# Recent Advances in Positive-Instance Driven Graph Searching +
## 4 A Unifying Take on Positive-Instance Driven Graph Searching  
Our goal is to generalize the algorithm that we just sketched in Section 3.2 to other graph measures such as treewidth and pathwidth. When we generalize from treedepth to other parameters, there are two main obstacles that we have to face. First, the sketched algorithm for treedepth \"guessed\" a root vertex in every iteration and glued already computed blocks to it. In more flexible graph decompositions such as tree decompositions, the root no longer is a single vertex but a _set of up to k vertices_. Clearly, we cannot guess such a set and, hence, have to compute it implicitly. Second, the treedepth algorithm explicitly carried the number of remaining searchers \(\rho\) around (they were part of the blocks). In more flexible graph measures, we may remove and reuse already placed searchers and, thus, have to encode this information in a different way. We will handle this issue by splitting the computation into two phases, where the first phase mainly computes a configuration graph (intuitively, this graph contains blocks for various values of \(\rho\)) and where the second phase then computes distances in this configuration graph (hence, computes best possible \(\rho\)-values for the blocks). However, let us postpone the fiddling with distance queries to Section 4.5 and focus solely on the more general search game in the first part of this section.  
We study graph searching in a setting proposed by [PERSON], [PERSON], and [PERSON] [62]. The input is again an undirected graph \(G=(V,E)\) and a number \(k\in\mathbb{N}\), and the question is whether a team of \(k\) searchers can catch an _invisible_ fugitive on \(G\) by the following set of rules: At the beginning, the fugitive picks a connected component \(C\) of \(G\) in which she hides--since the fugitive is invisible, in contrast to Section 3.2, the game is continued on \(G\) and _not_ on \(G[C]\) and we say that the set \(V\) is _contaminated_. In each round, the player now follows a similar procedure as in the previous game, but the searchers have a larger set of possible moves:  
1. The searchers perform one of the following: * _Place_ a searcher on a contaminated vertex; * _Remove_ a searcher from a vertex; * _Reveal_ the current position of the fugitive.
2. The fugitive responds as follows: * If the searchers _place_ or _remove_ a searcher, the fugitive adapts her connected component by adding or removing the vertex, respectively. (This may join multiple components or disconnect the current component, in which case the fugitive selects one of the resulting connected components). * If the searchers perform a _reveal_, the fugitive responds by uncovering her current connected component \(C\). The contaminated area is reduced to \(C\).  
We follow the same terminology as before, i. e, we say a contaminated vertex becomes _clean_ if a searcher is placed on it. In contrast to the previous game, a vertex \(v\) may now become _recontaminated_ if a searcher is removed from it and there is a contaminated vertex adjacent to \(v\). The searchers win the game if they manage to clean all vertices, i. e., if they catch the fugitive; the fugitive wins if, at any point, a recontamination occurs or if she can escape infinitely long. Note that this implies that the searchers have to catch the fugitive in a _monotone_ way. A priori, one could assume that the later condition gives the fugitive an advantage (recontamination could be necessary for the cleaning strategy); however, a crucial result in graph searching is that \"recontamination does not help\" in all variants of the game that we consider [59; 61; 76; 77; 78].