# Recent Advances in Positive-Instance Driven Graph Searching +
## Appendix A.1.1 From Tree Decompositions to Edge-Alternating Paths
Hence, for each component \(\Gamma\), we follow the universal edge to \(\Gamma\) and then proceed as above: first, we find a path \(P_{1}\) of existential edges from \(\Gamma\) to a configuration \(\Gamma_{1}\) with \(N(\Gamma_{1})\subseteq\iota(i)\cap\iota(j(\Gamma))\) and then a path \(P_{2}\) of existential edges from \(\Gamma_{1}\) to a configuration \(\Gamma_{2}\) with \(N(\Gamma_{2})\subseteq\iota(j(\Gamma))\). The same arguments as above imply that all configurations on these paths exist and that we arrive at a configuration \(\Gamma_{2}\) with \(N(\Gamma_{2})\subseteq\iota(j(\Gamma))\) and: \[\Gamma_{2}\subseteq\big{[}\bigcup_{j^{\prime}\in\operatorname{desc}(j(\Gamma ))}\iota(j^{\prime})\big{]}\setminus\iota(j(\Gamma)).\] This shows that we will eventually reach the leaves of the tree decomposition and, thus, some wining configuration. This is an edge-alternating path in \(\operatorname{colosseum}(G,k+1)\) and \(\operatorname{pit}(G,k+1)\). Furthermore, as each path from the root of \(T\) to some leaf of \(T\) containsat most \(q\) nodes with more than one children, this path is \(q\)-branched, as we use at most \(q\) universal edges from the initial configuration \(V\) to any used winning configuration for every induced directed path. Hence, we have found an edge-alternating path in \(\text{pit}(G,k+1)\) of cost at most \(q\). **Appendix A.1.2**. : From Edge-Alternating Paths to Tree Decompositions  
Let \(P\subseteq V(\text{pit}(G,k+1))\) be an edge-alternating \(q\)-branched path from the initial configuration \(V\) to a final configuration \(\{v^{*}\}\) in \(\text{pit}(G,k+1)\) with \(|N(\{v^{*}\})|\leq k\). We argue inductively on \(q\). * If \(q=0\), the path \(P\) does not use any universal edges. Let \(\pi=\pi_{1},\dots,\pi_{s}\) be any classical directed path from the initial configuration \(V\) to some winning configuration \(\{v^{*}\}\) in \(\text{pit}(G,k+1)\) that only uses vertices from \(P\). As the initial configuration is \(\pi_{1}=V\), the winning configuration is \(\pi_{s}=\{v^{*}\}\), and there are only existential edges \((C,C^{\prime})\) with \(|C^{\prime}|=|C|-1\) in \(\text{pit}(G,k+1)\), we know that \(|\pi_{i}|=|V|-i+1\), and thus \(s=|V|\). We say that vertex \(v\in V\) is _removed at time \(i\)_, if \(v\in\bigcap_{j=1}^{i}\pi_{j}\) and \(v\
ot\in\bigcup_{j=i+1}^{|V|}\pi_{j}\). We also say that \(v^{*}\) was removed at time \(|V|\). For \(i=1,\dots,|V|\), let \(v_{i}\) be the vertex removed at time \(i\). We will now construct a \(0\)-branched tree decomposition \((T,\iota)\), i. e., a path decomposition. As \(T\) is a path, let \(t_{1},\dots,t_{|V|}\) be the vertices on the path in their respective ordering with root \(t_{1}\). We set \(\iota(t_{i})=N(\pi_{i})\cup\{v_{i}\}\). For \(i=1,\dots,|V|-1\), there is an existential edge leading from \(\pi_{i}\) to \(\pi_{i+1}\) and thus \(|N(\pi_{i})|\leq k\). As \(\pi_{|V|}=\{v_{|V|}\}\) is a winning configuration, we also have \(|N(\pi_{|V|})|\leq k\). Hence, the resulting decomposition \(T\) has width at most \(k\). As \(T\) is a path, it is also \(0\)-branched. We now need to verify that \((T,\iota)\) is indeed a valid tree decomposition. As every vertex \(v\) is removed at some time \(i\), we have \(v=v_{i}\) and thus \(v\in\iota(t_{i})\). Hence, every vertex is in some bag. Let \(\{v_{i},v_{i^{\prime}}\}\) be any edge with \(i<i^{\prime}\). As \(v_{i^{\prime}}\in\pi_{i^{\prime}}\) and \(v_{i}\
ot\in\pi_{i^{\prime}}\), we have \(v_{i}\in N(\pi_{i^{\prime}})\) and thus \(\{v_{i},v_{i^{\prime}}\}\subseteq N(\pi_{i^{\prime}})\cup\{v_{i^{\prime}}\}= \iota(t_{i^{\prime}})\). Hence, every edge is in some bag. Finally, let \(v_{i}\in V\). Clearly, as \(v_{i}\in\pi_{1}\), \(v_{i}\in\pi_{2}\), \(\dots\), \(v_{i}\in\pi_{i-1}\), the first bag where \(v_{i}\) might appear is \(\iota(t_{i})\). Let \(v_{i^{\prime}}\in N(v_{i})\) be the neighbor of \(v_{i}\) that is removed at the latest time. If \(i^{\prime}<i\), we have \(N(v_{i})\cap\bigcup_{j=i+1}^{|V|}\pi_{j}=\emptyset\) and \(v_{i}\) thus only appears in \(\iota(t_{i})\).