Guarding a subgraph as a tool in pursuit-evasion games (Q2062677)

Pursuit-evasion games on a reflexive graph \(G\) are games in which several cops search a graph for a robber. Both characters move along the edges of \(G\) and the robber is captured if a cop steps on the vertex the intruder is on. This paper studies the idea of guarding a subgraph in a pursuit-evasion game. Guarding a subgraph \(H\) of \(G\) is defined as setting up \(H\) such that if the robber enters \(H\), he can be instantly captured. In this case, the cop can be thought of as a guard and the robber as an intruder. This paper formally introduces this strategy as an algorithm, proves a characterization of games when a single guard can win against several intruders, and most importantly, it introduces the idea of a robber shadow. This is defined as `the maximal set of vertices from which the cop parries the protected subgraph'. This paper shows that this shadow, and thus algorithms for a successful guard and for a successful intruder (if they exist), can be computed in polynomial time. Additionally, it is shown that the shadow functions generalize graph retractions.