A Game of COPS & ROBBERS

first designed by Mostafa Azizi, revised by Fan Chung Graham spring 2002




Description of the Game:

The Cop and Robber game is a very interesting game.

Two players, a cop (C), and a robber (R), compete on a fixed, finite undirected graph H.

First, the cop starts by placing himself at a node of his choice; then the robber does the same. After that, the two players alternate (beginning with the cop) moving to an adjacent node or choosing not to move. All moves are seen by both players. (Here we modified the original rules of Winkler by allowing the robber "not to move".)

The cop wins the game if he can CAPTURE the robber, that is,
move onto the node that is occupied by the robber or the robber (is forced to) move onto the node that is occupied by the cop .
The robbers wins if he is able to avoid being captured indefinitely. For example, the Cop can clearly win on PATHS and looses on CYCLES of length at least 4.

Also, the Cop wins when H has only one node, looped or not, and on a pair of connected nodes. If the graph is not connected, then the Robber wins.



Examples & Illusration of the Game:

 
  Here we give some examples of graphs:


One important thing to notice is that all of the above graphs are finite. In fact all are simple graphs except for #3. Graph #3 is not simple. Also notice that graph #5 is in two "pieces" so it is not connected. With this
game, we will concentrate on connected graphs with only one "piece", that means
graphs 1-4. (Unlike the orignial game of Winkler, the loops or multiple edges do not make a difference in our game.)

Now let us illustrate the cop and robber game. Given a finite simple connected graph,
the cop starts at one vertex, the robber at another. At his turn each must move along
an edge to an adjacent vertex or choose not to move. They alternate turns. The cop tries to land on the
robber (or have the robber land on him!) while, the robber tries to get away.

Now for a questions!
What is the smallest graph (i.e: smallest number of vertices) so that a single robber can always evade a single cop, no matter where they start?

Well, Graph #1 is too small. Graph #5 depends on the starting position. It seems that graph #2 is just right!.
A tree is a special kind of graph. Our graph #4 is an example of a tree. If a graph is a TREE, then the cop will ALWAYS catch the robber.


Structural Description:

Suppose that i and j are adjacent nodes of a graph H such that any other node ajacent to i is adjacent to j.
Then the map taking i to j, and every other node of H to itself, is a
homomorphism from H to H\{i}. We call this a fold of the graph H.


A finite graph H is dismantlable if there is a sequence of folds reducing H to
a graph with one node (looped or not). The name is chosen (in preference to
"cop-win") in order to stress the structure.

Try to prove the following theorem:

Theorem:

A graph is cop-win if and only if the graph is dismantlable.

This leads to an efficient algorithm for this rather complex game!

Describe an algorithm to decide if an input graph is cop-win or robber-win.

If the graph is cop-win, describe an algorithm for the cop to always catch the robber.

More questions and more cops:



References:

1. Richard Nowakawski and Peter Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math 43 (1983), 235-239.
2. Graham Brightwell and Peter Winkler, Gibbs measures and dismantlable graphs, J. Comb. Theory (Series B) 78 (2000), pp. 141-169. PostScript file
3. Bondy and Murty, Graph Theory with Applications, North Holland, 1976.
4. Harary, Graph Theory, Addison-Wesley, 1969.
5. Tero Harju: http://users.utu.fi/harju/exercises.ps.gz
6. H. Jem: http://hjem.get2net.dk/policeshooting/images/div.grafik/
7. M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Math 8 (1984), 1-12. (This paper includes a proof that 3 cops suffice for planar graphs.)