# Recent Advances in Positive-Instance Driven Graph Searching +
## 4 A Unifying Take on Positive-Instance Driven Graph Searching
### Distance Queries in Edge-Alternating Graphs  
We have just discussed how to compute the pit for a given graph and \(k\in\mathbb{N}\). The computation of graph measures such as treewidth now boils down to simple distance queries to this pit. To obtain an intuition of \"distance\" in edge-alternating graphs, think about such a graph as in our game and consider some vertex \(v\). There is always one active player that may decide to take _one_ existential edge (a fly-move in our game) or the player may decide to ask the opponent to make a move and, thus, has to handle _all_ universal edges (a reveal-move in our game). From the point of view of the active player, the distance is thus the _minimum_ over the _minimum_ of the distances of the existential edges and the _maximum_ of the universal edges. procedure discover(G, k)
2\(V(\text{pit}(G,k)):=\emptyset\)
3\(E(\text{pit}(G,k)):=\emptyset\)
4\(A(\text{pit}(G,k)):=\emptyset\)
5 initialize empty-queue
6
7//Phase I: compute Q
8 forv\(\in V(G)\)do
9 offer(\(\{v\}\), k-1)
10 end
11
12//Phase II: compute \(\mathcal{R}(Q)=V(\text{pit}(G,k))\)
13 whilequeue not empty do
14 extract C from-queue
15
16//reversefly-moves
17 forv\(\in\)N(C)do
18 offer(C\(\cup\{v\}\), k-1)
19 end
20
21//reversereal-moves
22 forC\(\in\)V(pit(G,k))do
23 ifinot intersect(C, C')then
24 offer(C\(\cup\)C', k)
25 end
26 end
27 end
28
29//Phase III: compute E and A
30 discoverEdges(\(V(\text{pit}(G,k))\), \(E(\text{pit}(G,k))\), \(A(\text{pit}(G,k))\))
31 return\(\big{(}V(\text{pit}(G,k)),E(\text{pit}(G,k)),A(\text{pit}(G,k))\big{)}\)
32 end
33 end  
Figure 5: The discover algorithm computes, given a graph \(G=(V,E)\) and an integer \(k\in\mathbb{N}\), the auxiliary graph \(\text{pit}(G,k)\). Using the positive-instance driven paradigm, only the elements of the pit are explored during this process. The executed subprocedures can be found in Figure 6.  
**Definition 2** (Edge-Alternating Distance). : _Let \(H=(V,E,A)\) be an edge-alternating graph with \(v\in V\) and \(Q\subseteq V\), let further \(c_{0}\in\mathbb{N}\) be a constant, and \(\omega_{E}\colon E\to\mathbb{N}\) and \(\omega_{A}\colon A\to\mathbb{N}\) be weight functions. The distance \(d(v,Q)\) from \(v\) to \(Q\) is inductively defined as \(d(v,Q)=c_{0}\) for \(v\in Q\) and otherwise:_  
\[d(v,Q)=\min\big{(}\min_{w\in N_{3}(v)}(d(w,Q)+\omega_{E}(v,w)),\ \max_{w\in N_{v}(v)}(d(w,Q)+\omega_{A}(v,w))\ \big{)}.\]  
**Lemma 4**. : _Given an acyclic edge-alternating graph \(H=(V,E,A)\), two weight functions \(\omega_{E}\colon E\to\mathbb{N}\) and \(\omega_{A}\colon A\to\mathbb{N}\), a source vertex \(s\in V\), a subset of the sinks \(Q\), and a constant \(c_{0}\in\mathbb{N}\). The value \(d(s,Q)\) can be computed in time \(O(|V|+|E|+|A|)\) and a corresponding edge-alternating path can be output in the same time._  
Proof of Lemma 4.: Since \(H\) is acyclic, we can compute a topological order of \((V,E\cup A)\) using the algorithm from [80]. We iterate over the vertices \(v\) in reversed order and compute the distance as follows. If \(v\) is a sink, we set:  
\[d(v,Q)= \begin{cases}c_{0}&\text{if }v\in Q;\\ \infty&\text{otherwise}.\end{cases} \]  
If \(v\) is not a sink, we have already computed \(d(w,Q)\) for all \(w\in N(v)\) and, hence, can compute \(d(v,Q)\) by the formula of the definition. Since this algorithm has to consider every edge once, the whole algorithm runs in time \(O(|V|+|E|+|A|)\). A path from \(s\) to \(Q\) of length \(d(s,Q)\) can be found by backtracking the labels starting at \(s\). Being able to answer distance queries in the pit yields an easy way of computing graph measures that have game theoretic characterizations [61; 62; 76]. For instance, if we wish to compute a tree decomposition (there is no bound on the number of branches nor on the depth), we seek a winning strategy that may use an unbounded number of reveals and fly-moves--hence, we just can look for _any_ path from the start configuration to \(Q\).