# Recent Advances in Positive-Instance Driven Graph Searching +
## Appendix A.1.1 From Tree Decompositions to Edge-Alternating Paths
If \(i<i^{\prime}\), then \(v_{i}\in\bigcap_{j=i+1}^{i^{\prime}}N(\pi_{j})\) and hence \(v_{i}\in\bigcap_{j=i+1}^{i^{\prime}}\iota(t_{j})\). * Now, assume that \(q\geq 1\) and that we can construct for every \(q^{\prime}<q\) a \(q^{\prime}\)-branched tree decomposition of width at most \(k\) from any \(q^{\prime}\)-branched edge-alternating path \(P\) in \(\text{pit}(G,k+1)\). Consider the directed acyclic subgraph \(H\) in \(\text{pit}(G,k+1)\) induced by \(P\). A configuration \(C\in V(H)\) is called a _universal configuration_, if \(N_{A}(C)\subseteq V(H)\) and a _top-level universal configuration_ with respect to some directed path \(\pi\) if \(C\) is the first universal configuration on \(\pi\). Note that we can reduce \(P\) in such a way that all directed paths \(\pi\) from the initial configuration \(V\) to some winning configuration \(\{v^{*}\}\) in \(H\) have the same top-level universal configuration, call it \(C^{*}\). Let \(V=\pi_{1},\dots,\pi_{i}=C^{*}\) be the shared existential path from \(V\) to \(C^{*}\) in \(H\) and let \(N_{A}(C^{*})=\{C_{1},\dots,C_{\ell}\}\) be the universal children of \(C^{*}\). Note that \(\{C_{1},\dots,C_{\ell}\}\subseteq P\) due to the definition of an edge-alternating path. For each child \(C_{j}\), the edge-alternating path \(P\) contains a directed path \(\pi^{(j)}\) from \(C_{j}\) to some final configuration in \(\text{pit}(G,k+1)\). Furthermore, each \(\pi^{(j)}\) contains at most \(q^{\prime}\leq q-1\) universal edges (otherwise, \(P\) would not be \(q\)-branched). Hence, by induction hypothesis, we can construct a \(q^{\prime}\)-branched tree decomposition \((T^{(j),\iota^{(j)})}\) for the subgraph induced by the vertices contained in the path \(\pi^{(j)}\) with root \(r^{(j)}\). Now, we use the same construction as above to construct a path \((T^{\prime}=(t^{\prime}_{1},\dots,t^{\prime}_{i}),t^{\prime})\) from \(\pi_{1},\dots,\pi_{i}\) and for each path \(\pi^{(j)}\) we add the root \(r^{(j)}\) of the \(q^{\prime}\)-branched tree decomposition \((T^{(j)},\iota(j))\) as a child of bag \(t_{i}\) to obtain our final tree decomposition \((T,\iota)\). As there is a universal edge from \(C^{*}\) to \(C_{j}\), we know that \(C_{j}\) is a component of \(C^{*}\). As all \((T^{(j)},\iota(j))\) are valid \(q-1\)-branched tree decompositions of width at most \(k\), we can thus conclude that \((T,\iota)\) is a valid \(q\)-branched tree decomposition of width \(k\). This concludes the proof of the claim. Combining the above claim with Theorem 1 for computing the pit, we conclude that we can check whether a graph \(G\) has \(q\)-branched-treewidth \(k\) in time \(O(|\operatorname{pit}(G,k+1)|^{2}\cdot|V|^{2})\). We note that the algorithm is fully constructive, as the obtained path (and, hence, the winning strategy of the searchers) directly corresponds to the desired decomposition. Since we have \(\operatorname{tw}(G)=\operatorname{tw}_{\infty}(G)\) and \(\operatorname{pw}(G)=\operatorname{tw}_{0}(G)\), the above results immediately imply the same statement for treewidth and pathwidth by checking \(d(V(G),k)<\infty\) or \(d(V(G),k)=0\), respectively.