# Recent Advances in Positive-Instance Driven Graph Searching +
## Appendix A.1.1 From Tree Decompositions to Edge-Alternating Paths
### Computing Treedepth Decompositions  
In order to show the statement for treedepth, we will require another claim for different weight functions. The proof idea is, however, very similar.  
**Claim A2**.: _Let \(G=(V,E)\) be a graph and \(k\in\mathbb{N}\). Define \(w_{E}\) as \((x,y)\mapsto 1\) and \(w_{A}\) as \((x,y)\mapsto 0\), and \(c_{0}=1\). Then we have \(d(V(G),Q)\leq k\) in \(\operatorname{pit}(G,k)\) if, and only if, \(\operatorname{td}(G)\leq k\)._  
Proof.: To prove the claim, we use an alternative representation of treedepth [58]. Let \(G=(V,E)\) be a graph with connected components \(C_{1},\ldots,C_{\ell}\), then:  
\[\operatorname{td}(G)=\begin{cases}1&\text{if }|V|=1;\\ \max_{i=1}^{\ell}\operatorname{td}(G[C_{i}])&\text{if }\ell\geq 2;\\ \min_{v\in V}\operatorname{td}(G[V\setminus\{v\}])+1&\text{otherwise.}\end{cases}\]  
Let us reformulate this definition a bit. Let \(C\subseteq V\) be a subset of the vertices and let \(C_{1},\ldots,C_{\ell}\) be the connected components of \(G[C]\). Define:  
\[\operatorname{td}^{*}(C)=\begin{cases}1&\text{if }|C|=1;\\ \max_{i=1}^{\ell}\operatorname{td}^{*}(C_{i})&\text{if }\ell\geq 2;\\ \min_{v\in C}\operatorname{td}^{*}(C\setminus\{v\})+1&\text{otherwise.}\end{cases}\]  
Obviously, \(\operatorname{td}(G)=\operatorname{td}^{*}(V)\). We proof that for any \(C\subseteq V\) we have \(d(C,Q)=\operatorname{td}^{*}(C)\) in \(\operatorname{pit}(G,k)\) for every \(k\geq\operatorname{td}(G)\) and \(d(C,Q)\geq\operatorname{td}^{*}(C)\) for all \(k<\operatorname{td}(G)\).  
For the first part, we consider the vertices of \(\operatorname{pit}(G,k)\) in inverse topological order and prove the claim by induction. The first vertex \(C_{0}\) is in \(Q\) and thus \(d(C_{0},Q)=c_{0}=1\). Since the vertices in \(Q\) represent sets of cardinality \(1\), we have \(d(C_{0},Q)=\operatorname{td}^{*}(C_{0})\). For the inductive step, consider \(C_{i}\) and first assume it is not connected in \(G\). Then  
\[d(C_{i},Q) =\max_{C_{j}\in N_{V}(C_{i})}\left(d(C_{j},Q)+w_{A}(C_{i},C_{j})\right)\] \[=\max_{C_{j}\in N_{V}(C_{i})}d(C_{j},Q)\] \[=\max_{C_{j}\text{ is a component in }G[C_{i}]}\operatorname{td}^{*}(C_{j})\] \[=\operatorname{td}^{*}(C_{i}).\]  
Note that there could, of course, also be existential edges leaving \(C_{i}\). However, since the universal edges are \"for free\", for every shortest path that uses an existential edge at \(C_{i}\), there is also one that first uses the universal edges.  
For the second case, that is \(C_{i}\) is connected, observe that \(C_{i}\) is not incident to any universal edge. Therefore, we obtain:  
\[d(C_{i},Q) =\min_{v\in C_{i}}\big{(}d(C_{i}\setminus\{v\},Q)+w_{E}(C_{i},C_{i} \setminus\{v\})\big{)}\] \[=\min_{v\in C_{i}}\big{(}d(C_{i}\setminus\{v\},Q)+1\big{)}\] \[=\min_{v\in C_{i}}\big{(}\operatorname{td}^{*}(C_{i}\setminus\{v \})+1\big{)}\] \[=\operatorname{td}^{*}(C_{i}).\]  
This completes the part of the proof that shows \(d(C,Q)=\operatorname{td}^{*}(C)\) for \(k\geq\operatorname{td}(G)\). We are left with the task to argue that \(d(C,Q)\geq\operatorname{td}^{*}(C)\) for all \(k<\operatorname{td}(G)\). This follows by the fact that for every \(k^{\prime}<k\) we have that \(\operatorname{pit}(G,k^{\prime})\) is an induced subgraph of \(\operatorname{pit}(G,k)\). Therefore, the distance can only increase in the pit for a smaller \(k\)--in fact, the distance can even become infinity if \(k<\operatorname{td}(G)\).  
Again, combining the claim with Theorem 3 yields the statement of the theorem for treedepth.