# Recent Advances in Positive-Instance Driven Graph Searching +
## 4 A Unifying Take on Positive-Instance Driven Graph Searching
### Fighting in the Pit  
The sketched algorithms have running time proportional to the size of the arena and the colosseum. Both of these auxiliary graphs might be large, as the arena has fixed size of order \(O(n^{k+1})\) while the colosseum may even have size \(O(2^{n})\). Additionally, both graphs can contain unnecessary configurations, that is, configurations not part of the winning region. In the light of dynamic programming, this is the same as listing all possible configurations, and in the light of positive-instance driven dynamic programming, we would like to list only the positive instances--which is exactly the winning region \(\mathcal{R}(Q)\). The _pit_\(\operatorname{pit}(G,k)\) inside the colosseum is now formally defined as the subgraph of \(\operatorname{colosseum}(G,k)\) induced by \(\mathcal{R}(Q)\), that is, as the induced subgraph on the winning region. The key insight is that \(|\operatorname{pit}(G,k)|\) may be smaller than \(|\operatorname{colosseum}(G,k)|\) or even \(|\operatorname{area}(G,k)|\) on various graph classes. Our primary goal for this section will therefore be the development of an algorithm that computes the pit in time depending only on _the size of the pit_ (rather the size of the arena or the colosseum). The algorithm traverses the colosseum \"backwards\" starting from the winning configurations \(Q\) and uncovering \(\mathcal{R}(Q)\) layer by layer. In order to achieve this, we need to compute the predecessors of a block \(C\). This is easy if \(C\) was reached by a fly-move as we can simply enumerate the \(n\) possible predecessors. Reversing a reveal-move, that is, finding the universal predecessors, is significantly more involved. A simple approach is to test for every subset of already explored configurations if we can \"glue\" them together--as we did in the sketched algorithm in Section 3.2. However, this results in an even worse runtime of \(2^{|\operatorname{pit}(G,k)|}\). To avoid this exponential blow-up, we require the following structural property of the colosseum. **Definition 1** (Universal Consistent). : _We say that an edge-alternating graph \(H=(V,E,A)\) is universal consistent with respect to a set \(Q\subseteq V\) if for all \(v\in V\setminus Q\) with \(v\in\mathcal{R}(Q)\) and \(N_{\forall}(v)=\{w_{1},\ldots,w_{r}\}\) we have (1) \(N_{\forall}(v)\subseteq\mathcal{R}(Q)\) and (2) for every \(I\subseteq\{w_{1},\ldots,w_{r}\}\) with \(|I|\geq 2\) there is a vertex \(v^{\prime}\in V\) with \(N_{\forall}(v^{\prime})=I\) and \(v^{\prime}\in\mathcal{R}(Q)\)._  
Intuitively, Definition 1 implies that for every vertex with high universal-degree, there is a set of vertices that can be arranged in a tree-like fashion to realize the same adjacency relation. This allows us to glue only two configurations at a time and, thus, removes the exponential dependency. The definition is illustrated in Example 1. **Example 1**. : _Consider the following three edge-alternating graphs, where black edges are existential and the blue edges are universal. The set \(Q\) contains a single vertex that is highlighted. From left to right: the first graph is universal consistent, the second and third one are not. The second graph conflicts the condition that \(v\in\mathcal{R}(Q)\) implies \(N_{\forall}(v)\subseteq\mathcal{R}(Q)\), as the vertex on the very left is contained in \(\mathcal{R}(Q)\) by the top path, while its universal neighbor on the bottom path is not contained in \(\mathcal{R}(Q)\). The third graph conflicts the condition that \(N_{\forall}(v)=\{w_{1},\ldots,w_{r}\}\) implies that for every \(I\subseteq\{w_{1},\ldots,w_{r}\}\) with \(|I|\geq 2\) there is a vertex \(v^{\prime}\in V\) with \(N_{\forall}(v^{\prime})=I\) and \(v^{\prime}\in\mathcal{R}(Q)\) as witnessed by the vertex with three outgoing universal edges._  
**Lemma 3**. : _For every graph \(G\) and number \(k\), the edge-alternating graph \(\operatorname{coloseum}(G,k)\) is universal consistent._  
Proof.