# Recent Advances in Positive-Instance Driven Graph Searching +
## 4 A Unifying Take on Positive-Instance Driven Graph Searching
### Building the Colosseum  
We are now ready to define the colosseum. As for the arena, we could define it as an alternating graph. However, as only the searchers perform actions in the simplified game,we find it more natural to express this game as an _edge-alternating graph_--a generalization of alternating graphs. An edge-alternating graph is a triple \(H=(V,E,A)\) consisting of a _vertex set_\(V\), an existential edge relation \(E\subseteq V\times V\), and a universal edge relation \(A\subseteq V\times V\). The neighborhoods of a vertex \(v\) are the existential neighborhood \(N_{\exists}(v)=\{\,w\mid(v,w)\in E\,\}\), the universal neighborhood \(N_{\forall}(v)=\{\,w\mid(v,w)\in A\,\}\), and the complete neighborhood \(N_{H}(v)=N_{\exists}(v)\cup N_{\forall}(v)\). An _edge-alternating \(s\)-\(t\)_-path is a set \(P\subseteq V\) such that (i) \(s,t\in P\) and (ii) for all \(v\in P\) with \(v\
eq t\) we have either \(N_{\exists}(v)\cap P\
eq\emptyset\) or \(\emptyset\
eq N_{\forall}(v)\subseteq P\) or both. We write \(s\prec t\) if such a path exists and define \(\mathcal{R}(Q)=\{\,v\mid v\in Q\vee(\exists w\in Q\cdot v\prec w)\,\}\) for \(Q\subseteq V\) as the set of vertices on edge-alternating paths leading to \(Q\). We say that an edge-alternating \(s\)-\(t\)-path \(P\) is \(q\)-_branched_ if (i) \(H\) is acyclic and (ii) every (classical) directed path \(\pi\) from \(s\) to \(t\) in \(H\) with \(\pi\subseteq P\) uses at most \(q\) universal edges.  
For \(G=\big{(}V(G),E(G)\big{)}\) and \(k\in\mathbb{N}\), the colosseum\((G,k)\) is the edge-alternating graph \(H\) with \(V(H)=\{\,C\mid\emptyset\
eq C\subseteq V(G)\,\big{|}\,N_{G}(C)\mid\leq k\,\}\) and the following edge sets: for all pairs \(C,C^{\prime}\in V(H)\) there is an existential edge \(e=(C,C^{\prime})\in E(H)\) if, and only if, \(C\setminus\{v\}=C^{\prime}\) for some \(v\in C\) and \(|N_{G}(C)|<k\); furthermore, for all \(C\in V(H)\) with at least two components \(C_{1},\ldots,C_{\ell}\) we have universal edges \((C,C_{i})\in A(H)\).  
The nodes of the colosseum are called _blocks_ and, thinking of Section 3.2, we have \(V(H)=\mathcal{B}(G,k)\) (but note that the definition of \"block\" has slightly changed). The _start configuration_ of the game is the block \(C=V(G)\), i. e., all vertices are contaminated. We define \(Q=\{\,v\}\subseteq V(G)\colon|N_{G}(\{v\})|<k\,\}\) to be the set of _winning configurations_, as at least one searcher is available to catch the fugitive. Therefore, the searchers have a winning strategy if, and only if, \(V(G)\in\mathcal{R}(Q)\) and we will therefore refer to \(\mathcal{R}(Q)=\mathcal{R}(G,k)\) as the _winning region_ (we did so similarly in Section 3.2, but we did not have the notation of edge-alternating graphs then). Observe that the colosseum is acyclic (that is, the digraph \((V(H),E(H)\cup A(H))\) is acyclic) as we have for every edge \((C,C^{\prime})\) that \(|C|>|C^{\prime}|\), and observe that \(Q\) is a subset of the sinks of this graph. Hence, we can test if \(V(G)\in\mathcal{R}(Q)\) in time \(O(|\operatorname{colosseum}(G,k))|)\). Finally, note that the size of \(\operatorname{colosseum}(G,k)\) may be of order \(2^{n}\) rather than \(n^{k+1}\), giving us a slightly worse overall runtime. This larger structure is required to encode that the fugitive is invisible.