# Recent Advances in Positive-Instance Driven Graph Searching +
## 3 A Gentle Introduction to Positive-Instance Driven Graph Searching
### Simple Positive-Instance Driven Graph Searching  
By Fact 1, it is sufficient to compute the set \(\mathcal{R}(G,k)\) in order to test whether the treedepth of \(G\) is at most \(k\). One way of doing so would be to first compute \(\mathcal{B}(G,k)\), then build an auxiliary graph on top of this set, and finally compute \(\mathcal{R}(G,k)\) by solving reachability queries on this auxiliary graph. We can estimate the number of configurations with \(|\,\mathcal{B}(G,k)|\leq(k+1)\cdot n^{k+1}\), as there are \(n^{k}\) possible ways of placing \(k\) searchers on an \(n\)-vertex graph--at most \(n\) connected components adjacent to a separator--and we have \(\rho\in\{0,\ldots,k\}\). Therefore, the sketched algorithm achieves a run time of \(n^{O(k)}\), which is not feasible in practice for even moderate values of \(k\). To make the game theoretic approach feasible, we present an _output-sensitive_ algorithm that computes just \(\mathcal{R}(G,k)\)--without \"touching\" the rest of \(\mathcal{B}(G,k)\). Figure 3 illustrates why we may hope that \(\mathcal{R}(G,k)\) is smaller than \(\mathcal{B}(G,k)\). In the remainder of this section, we will develop some intuition about how to compute the set \(\mathcal{R}(G,k)\). The formal details are postponed to the unifying version of the algorithm in the next section. Surely, we cannot start at some block, say \((V,k)\), and just simulate the game in a top-down fashion--we could touch a lot of blocks in \(\mathcal{B}(G,k)\setminus\mathcal{R}(G,k)\) without even noticing it (in Figure 3, that would mean starting a graph traversal from \(s\), which could explore any leg of the spider). After all, we do not know whether \((V,k)\in\mathcal{R}(G,k)\). We do know, however, that \((\emptyset,0)\) is a winning configuration (vertex \(t\) in Figure 3). So, let us start with the set \(\mathcal{R}=\{\,(\emptyset,0)\,\}\) and then try to grow it to \(\mathcal{R}(G,k)\) in a bottom-up fashion. We can first ask which configurations of the game lead to \((\emptyset,0)\), i.e., what are configurations in which the searchers immediately win in the next round? These are the configurations \((\{v\},1)\) with \(|N(v)|<k\), as in these the searchers can surround the fugitive and have a searcher left to place it on top of her (in Figure 3, this corresponds to the predecessor of \(t\)). Now, assume that we have currently a set \(\mathcal{R}\subseteq\mathcal{R}(G,k)\) that had already grown a little. What does a configuration \((C,\rho)\in\mathcal{R}(G,k)\setminus\mathcal{R}\) that is \"close to\" \(\mathcal{R}\) look like (that is, we wish to traverse the \(s\)-\(t\)-path of Figure 3 in reverse direction)? The set \(C\) is connected by definition and, since the searchers have a winning strategy from \((C,\rho)\), there is a vertex \(v\in C\) such that \(G[C\setminus\{v\}]\) has connected components \(C_{1},\ldots,C_{q}\) (\(q=1\) is possible) with \((C_{i},\rho-1)\in\mathcal{R}\) for all \(i\in\{1,\ldots,q\}\). To find \((C,\rho)\), we first guess the vertex \(v\), scan  
Figure 3: A directed spider with \(2^{n}\) legs each of length \(n\) that could be the auxiliary graph of a graph searching game—i. e., the vertex set is \(\mathcal{B}(G,k)\). Assume \(s\) is the start configuration and, for the sake of argument, that \(t\) is the sole winning configuration. Then \(\mathcal{R}(G,k)\) contains only \(n\) elements, while the whole game has \(2^{n}\cdot n\) configurations. the sets of pairwise non-intersecting blocks \(X\subseteq\setset{(C^{\prime},\rho^{\prime})\in\mathcal{R}}{\mid v\in N_{G}(C^{ \prime})\wedge\rho^{\prime}<\rho}\), and generate the new blocks \(\setset{(\bigcup_{(C^{\prime},\rho^{\prime})\in X}C^{\prime}\cup\{v\},1+\max_{(C ^{\prime},\rho^{\prime})\in X}\rho^{\prime}})\). Note that we can prune a set \(X\) if \(\big{|}\big{(}N_{G}(\bigcup_{(C^{\prime},\rho^{\prime})\in X}C^{\prime})\big{|} >k-\max_{(C^{\prime},\rho^{\prime})\in X}\rho^{\prime},\) as this neighborhood has to be cleaned by the searchers before they clean one of the components \(C^{\prime}\).