Cop-win graph

The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order.

This can be proved by mathematical induction, with a one-vertex graph (trivially won by the cop) as a base case.

By the induction hypothesis, the cop has a winning strategy on the graph formed by removing v, and can follow the same strategy on the original graph by pretending that the robber is on the vertex that dominates v whenever the robber is actually on v. Following this strategy will result either in an actual win of the game, or in a position where the robber is on v and the cop is on the dominating vertex, from which the cop can win in one more move.

[2][4] A cop following this inductive strategy on a graph with n vertices takes at most n moves to win, regardless of starting position.

For, in a graph with no dominated vertices, if the robber has not already lost, then there is a safe move to a position not adjacent to the cop, and the robber can continue the game indefinitely by playing one of these safe moves at each turn.

[2][8] Additionally, if v is a dominated vertex in a cop-win graph, then removing v must produce another cop-win graph, for otherwise the robber could play within that subgraph, pretending that the cop is on the vertex that dominates v whenever the cop is actually on v, and never get caught.

It follows by induction from these two principles that every finite cop-win graph is dismantlable.

Each vertex in the strong product corresponds to a pair of vertices in each of two factor graphs.

Then, while staying in pairs whose first component is the same as the robber, the cop can play to win in the second of the two factors.

A dismantling order can be found by a simple greedy algorithm that repeatedly finds and removes any dominated vertex.

[13] To speed up its computations, Spinrad's algorithm uses a subroutine for counting neighbors among small blocks of log2 n vertices.

These numbers allow the algorithm to count, for any two vertices x and y, how much B contributes to the deficit of x and y, in constant time, by a combination of bitwise operations and table lookups.

Analogously, it is possible to construct computable countably infinite cop-win graphs, on which an omniscient cop has a winning strategy that always terminates in a finite number of moves, but for which no algorithm can follow this strategy.

On such graphs, every algorithm for choosing moves for the cop can be evaded indefinitely by the robber.

Such a move cuts off part of the polygon which the robber can never double back to reach.

[22] Bonato and Nowakowski describe this game intuitively as the number of ghosts that would be needed to force a Pac-Man player to lose, using the given graph as the field of play.

[23] The game used to define cop number should be distinguished from a different cops-and-robbers game used in one definition of treewidth, which allows the cops to move to arbitrary vertices rather than requiring them to travel along graph edges.

[24] The game with a single cop, and the cop-win graphs defined from it, were introduced by Quilliot (1978).