# Recent Advances in Positive-Instance Driven Graph Searching +
## 3 A Gentle Introduction to Positive-Instance Driven Graph Searching
### Graph Searching  
Many graph decompositions have game theoretic characterizations in the form of _vertex pursuit-evasion games_[74]. Such games, which are also known as _graph searching_ or _cops and robber_, are played by two players on an undirected graph \(G=(V,E)\). In the game for treedepth, the first player places a team of \(k\)_searchers_ iteratively on the vertices of \(G\), while the second player controls a single _fugitive_ that hides in a connected component. The game is played in rounds as follows [61; 75]: Initially, the fugitive hides in the vertex set \(C=V\) (which we assume to be connected). The vertices in \(C\) are said to be _contaminated_. In each round, both players perform one action:  
1. The searchers pick a vertex \(v\in C\) on which they want to place the next searcher. We say they _clean_ the vertex \(v\).
2. The fugitive responds by picking a component \(C^{\prime}\) of \(G[C\setminus\{v\}]\). The contaminated area is reduced to \(C^{\prime}\) and the game proceeds only on this subgraph.  
The game ends when the contaminated area shrinks to the empty set or if the searchers have placed all \(k\) members of their team and \(C\) is still non-empty. In the first case, the graph was _cleanted_ and the fugitive was _caught_; in the second case, the fugitive _escaped_. The searchers win if they catch the fugitive, otherwise the fugitive wins. Note that in this version of the game, the searchers are not allowed to remove an already placed searcher from the graph. The game is therefore monotone and always ends after, at most, \(k\) rounds. Further observe that the fugitive is _visible_ in the sense that the searchers know in which connected component she hides--in contrast, an invisible fugitive could hide in subgraphs that are not connected (which notably complicates the arguments). The game is illustrated in Figure 2 on a small graph with eight vertices.  
The configurations of this game are _blocks_, which are tuple \((C,\rho)\) with \(\rho\in\mathbb{N}\) and \(C\subseteq V\) being a connected subgraph with \(|N(C)|+\rho\leq k\). Informally, \(C\) is the (connected) contaminated area, and \(\rho\) is the number of remaining searchers. We require \(|N(C)|+\rho\leq k\) as the neighborhood of \(C\) has to be cleaned in order to have \(C\) as contaminated area. We denote the set of blocks of the game played on a graph \(G\) with \(k\) searchers by \(\mathcal{B}(G,k)\). Two  
Figure 2: An illustration of the graph searching game for treedepth on the 8 vertex graph shown at the very top. Vertices that contain a green dot are currently _contaminated_. The searchers will _place_ a searcher on the vertex with a red circle in the next round. The _cleaned_ vertices (on which a searcher stands) are filled with blue. The arrows indicate the various choices of the fugitive. The diagram proves that 4 searchers have a winning strategy on this specific graph.  
blocks \((C_{1},\rho_{1})\) and \((C_{2},\rho_{2})\)_intersect_ if \(C_{1}\cap C_{2}\
eq\emptyset\), \(N_{G}(C_{1})\cap C_{2}\
eq\emptyset\) or \(C_{1}\cap N_{G}(C_{2})\
eq\emptyset\). The _start configuration_ of the game is \((V,k)\) and the _winning configurations_ for the searchers are \((\emptyset,\rho\geq 0)\). We say the searchers have a _winning strategy_ on a block \((C,\rho)\) if, starting with configuration \((C,\rho)\), they can ensure to reach a winning configuration no matter how the fugitive acts. The set of blocks that guarantee such a strategy is the _winning region_, which we denote by \(\mathcal{R}(G,k)\subseteq\mathcal{B}(G,k)\)--the elements in this region are said to be _positive_. The connection between the game and the width measure treedepth is established by the following fact:  
**Fact 1** ([61]).: _Let \(G=(V,E)\) be a graph and \(k\in\mathbb{N}\). Then \((V,k)\in\mathcal{R}(G,k)\Longleftrightarrow\operatorname{td}(G)\leq k\)._