# Recent Advances in Positive-Instance Driven Graph Searching +
## Appendix A.1.1 From Tree Decompositions to Edge-Alternating Paths  
Let \((T,\iota)\) be a \(q\)-branched tree decomposition of \(G=(V,E)\) of width \(k\). Without loss of generality, we can assume that \(G\) is connected. We will show how to construct an edge-alternating path from the start configuration \(V\) of cost at most \(q\) in \(\operatorname{colosseum}(G,k+1)\). As described above, this is also an edge-alternating path with the same costs in \(\operatorname{pit}(G,k+1)\). The first existential edge from \(V\) leads to the configuration \(V\setminus\iota(r)\), where \(r\) is the root of \(T\). Observe that we clearly have \(N(V\setminus\iota(r))\subseteq\iota(r)\). Suppose a configuration \(C\) was reached with \(N(C)\subseteq\iota(i)\in V(\operatorname{colosseum}(G,k+1))\) for some node \(i\in T\) and we have:  
\[C\subseteq\big{[}\bigcup_{j\in\operatorname{desc}(i)}\iota(j)\big{]} \setminus\iota(i).\]  
Clearly, for \(i=r\), this assumption holds trivially. If \(i\) is a leaf in \(T\), there are no more descendants and thus \(C=\emptyset\). Hence, we have reached a winning configuration in \(\operatorname{colosseum}(G,k+1)\). Now, suppose that \(i\) is a non-leaf node. We distinguish two cases:  
* If \(i\) has exactly one child \(j\), we can find a path \(P_{1}\) of existential edges leading from \(C\) to a configuration \(C_{1}\) with \(N(C_{1})\subseteq\iota(i)\cap\iota(j)\). Moreover, we can also find a path \(P_{2}\) of existential edges from \(C_{1}\) to a configuration \(C_{2}\) with \(N(C_{2})\subseteq\iota(j)\). The path \(P_{1}\) will be constructed by iteratively removing all vertices \(v\in C\) with \(N(v)\cap\iota(i)\setminus\iota(j)|\
eq\emptyset\). For the remaining vertices \(C_{1}\), we have \(N(C_{1})\subseteq\iota(i)\cap\iota(j)\). If all configurations that we aim to visit on \(P_{1}\) exist, the corresponding edges also exist by definition. Assume that we are in some configuration \(C^{\prime}\) with \(N(C^{\prime})\cap[\iota(i)\setminus\iota(j)]\
eq\emptyset\) and want to remove a vertex \(v\in C^{\prime}\) with \(N(v)\cap[\iota(i)\setminus\iota(j)]\
eq\emptyset\), but \(C^{\prime}\setminus\{v\}\
ot\in V(\operatorname{colosseum}(G,k+1))\). By definition of \(\operatorname{colosseum}(G,k+1)\), this means that \(|N(C^{\prime}\setminus\{v\})|\geq k+2\). As we wanted to remove \(v\), we have \(N(v)\cap\iota(i)\
eq\emptyset\). As \(N(C^{\prime}\setminus\{v\})\subseteq N(C^{\prime})\cup\{v\}\) and \(|N(C^{\prime}\setminus\{v\})|\geq k+2\), we know that there is some \(u\in C^{\prime}\) with \(v\in N(u)\). Fact A.1 implies that \(v\in\iota(i)\cap\iota(j)\), a contradiction and, hence, all configurations in \(P_{1}\) exist. Similarly, we construct \(P_{2}\) by iteratively removing all vertices in \(\iota(j)\) from \(C_{1}\). It is easy to see that the neighborhood of the visited configurations will always be a subset of \(\iota(j)\) and, hence, all configurations on this path exist. We have arrived at a configuration \(C_{2}\) with \(N(C_{2})\subseteq\iota(j)\) and due to Fact A.1: \[C_{2}\subseteq\big{[}\bigcup_{j^{\prime}\in\operatorname{desc}(j)}\iota(j^{ \prime})\big{]}\setminus\iota(j).\]
* If node \(i\) has a set of children \(J\) with \(|J|\geq 2\), we will use universal edges. Let \(\mathcal{C}\) be the connected components of \(G[\bigcup_{j\in\operatorname{desc}(i)}\iota(j)\setminus\iota(i)]\). We claim that for each component \(\Gamma\in\mathcal{C}\) there is a unique index \(j(\Gamma)\in J\) such that \(\Gamma\cap\iota(j(\Gamma))\
eq\emptyset\). If no such index exists, we have \(\iota(j)=\iota(i)\). We can iteratively remove such bags \(\iota(j)\) until this cannot happen anymore. If two indices \(j_{1},j_{2}\in J\) exist with \(\iota(j_{1})\cap\Gamma\
eq\emptyset\) and \(\iota(j_{2})\cap\Gamma\
eq\emptyset\), the connectivity property implies that \(\iota(i)\cap\Gamma\
eq\emptyset\), a contradiction to our assumption.