# Recent Advances in Positive-Instance Driven Graph Searching +
## 4 A Unifying Take on Positive-Instance Driven Graph Searching
### Fighting in the Pit
: For the first property, observe that \"reveals do not harm\": Searchers that can catch the fugitive without knowing where she hides, certainly can do so if they know. For the second property, consider any configuration \(C\in V(H)\) that has universal edges to \(C_{1},\ldots,C_{\ell}\). By definition, we have \(|N_{G}(C)|\leq k\) and \(N_{G}(C_{i})\subseteq N_{G}(C)\) for all \(1\leq i\leq\ell\). Therefore, we have for every \(I\subseteq\{1,\ldots,\ell\}\) and \(C^{\prime}=\cup_{i\in I}C_{i}\) that \(N_{G}(C^{\prime})\subseteq N_{G}(C)\) and \(|N_{G}(C^{\prime})|\leq k\) and, thus, \(C^{\prime}\in V(H)\). The algorithm for computing the pit, see Figures 5 and 6, runs in three phases: it first computes the set \(Q\) of winning configurations; then the winning region \(\mathcal{R}(Q)\) (the vertices of \(\operatorname{pit}(G,k)\)); and finally, it computes the edges of \(\operatorname{pit}(G,k)\). **Theorem 1**. : _The algorithm discover(\(G\),\(k\)) finishes in at most \(O\big{(}|\ \mathcal{R}(Q)|^{2}\cdot|V|^{2}\big{)}\) steps and correctly outputs \(\operatorname{pit}(G,k)\)._  
Proof. : The algorithm computes \(Q\) in phase I, the winning region \(\mathcal{R}(Q)\) in phase II, and the edges of \(\operatorname{coloseum}(G,k)[\mathcal{R}(Q)]\) in phase III. First observe that \(Q\) is correctly computed in phase I by the definition of \(Q\). For the correctness of the second phase, we show that the computed set \(V(\operatorname{pit}(G,k))\) equals \(\mathcal{R}(Q)\). Let us refer to the set \(V(\operatorname{pit}(G,k))\) during the computation as \(K\) and observe that this is exactly the set of vertices inserted into the queue. We first show \(K\subseteq\mathcal{R}(Q)\) by induction over the \(i\)th inserted vertex. The first vertex \(C_{1}\) is in \(\mathcal{R}(Q)\) as \(C_{1}\in Q\). Now, consider a \(C_{i}\in K\). It was either added in Line 18 or Line 24. In the first case, there was a vertex \(\hat{C}_{i}\in K\) such that \(C_{i}=\hat{C}_{i}\cup\{v\}\) for some \(v\in N(\hat{C}_{i})\). By the induction hypothesis we have \(\hat{C}_{i}\in\mathcal{R}(Q)\) and by the definition of the colosseum we have \((C_{i},\hat{C}_{i})\in E(H)\) and, thus, \(C_{i}\in\mathcal{R}(Q)\). In the second case, there were vertices \(\hat{C}_{i},\hat{C}_{i}\in K\) with \(C_{i}=\hat{C}_{i}\cup\hat{C}_{i}\)By the induction hypothesis, we have again \(\hat{C}_{i},\hat{C}_{i}\in\mathcal{R}(Q)\). Let \(t_{1},\ldots,t_{\ell}\) be the connected components of \(\hat{C}_{i}\) and \(\hat{C}_{i}\). Since the colosseum is universal consistent with respect to \(Q\) by Lemma 3, we have \(t_{1},\ldots,t_{\ell}\in\mathcal{R}(Q)\). By the definition of the colosseum, we have \(N_{\forall}(C_{i})=t_{1},\ldots,t_{\ell}\) and, thus, \(C_{i}\in\mathcal{R}(Q)\). To see \(\mathcal{R}(Q)\subseteq K\), consider for a contradiction the vertices of \(\mathcal{R}(Q)\) in reversed topological order (recall that the colosseum is acyclic) and let \(C\) be the first vertex in this order with \(C\in\mathcal{R}(Q)\) and \(C\
ot\in K\). If \(C\in Q\), we have \(C\in K\) by phase I and are complete, so assume otherwise. Since \(C\in\mathcal{R}(Q)\), we have either \(N_{\exists}(C)\cap\mathcal{R}(Q)\
eq\emptyset\) or \(\emptyset\
eq N_{\forall}(C)\subseteq\mathcal{R}(Q)\). In the first case, there is a block \(\tilde{C}\in\mathcal{R}(Q)\) with \((C,\tilde{C})\in E(H)\). Block \(\tilde{C}\), thus, precedes \(C\) in the reversed topological order and, by the choice of \(C\), we have \(\tilde{C}\in K\). Therefore, at some point, \(\tilde{C}\) is extracted from the queue and, in Line 18, \(C\) would be added to \(K\), a contradiction. In the second case, there are vertices \(t_{1},\ldots,t_{\ell}\in\mathcal{R}(Q)\) with \(N_{\forall}(C)=\{t_{1},\ldots,t_{\ell}\}\). By the choice of \(C\), we have again \(t_{1},\ldots,t_{\ell}\in K\). Since \(H\) is universal consistent with respect to \(Q\), we have for every \(I\subseteq\{1,\ldots,\ell\}\) that \(\bigcup_{i\in I}t_{i}\) is contained in \(\mathcal{R}(Q)\).