Solving the Cops and Robbers Graph Pursuit Game

Cops and Robbers is a perfect-information pursuit-evasion game on a graph. Determining if k cops can always capture a robber is the Cop Number problem.

Game Setup

• Graph G = (V, E): Vertices = locations; Edges = moves.
• Cops (k): Choose starting vertices. Move one cop per turn to adjacent vertex (or stay).
• Robber (1): Chooses start after cops. Moves to adjacent vertex (or stays) each turn.
• Capture: Cop occupies same vertex as robber. Cops win if capture guaranteed; robber wins if evades forever.

Solving Approach (Theoretical)

1. Compute Cop Number c(G): Minimum cops needed to guarantee capture.
   • c(G) = 1 ⇔ Graph is dismantlable (has a corner vertex—neighborhood subset of another). Trees, chordal graphs, interval graphs have c(G)=1.
   • c(G) ≤ 3 for planar graphs (Aigner & Fromme, 1984).
   • c(G) can be arbitrarily large (Meyniel's conjecture: c(G) = O(√n) — open).
2. Algorithmic (Small Graphs): Model as reachability game on product graph (cop positions × robber position). Solve via retrograde analysis / BFS on state space (exponential in k).
3. Heuristics for Play:
   • Cops: Guard dominating sets, centroids, cut-vertices; herd robber toward dead ends.
   • Robber: Stay in high-girth areas, avoid articulation points, exploit cop coordination gaps.

Practical Tools

• NetworkX (Python): `networkx.algorithms.approximation.cops_and_robbers` (heuristic).
• Cops and Robbers Simulator (web): Search for interactive visualizations.
• Literature: "The Game of Cops and Robbers on Graphs" (Bonato & Nowakowski, 2011) — definitive text.

For a specific graph, draw it, identify corners/dominating sets, and simulate cop strategies manually or with code.