Cops and Robbers is an actively studied topic in graph theory and intersects with graph searching, where we must capture, avoid, or contain agents in a network. Think of Pac-Man, or the spread of emotional contagion in social networks, or driverless cars, and you are in the realm of graph searching.

Cops and Robbers is a game played on graphs between an opposing set of cops and a single robber. The cops begin the game by moving to a set of vertices, with the robber then choosing a vertex to occupy. The players move from vertex-to-vertex along edges. The cops win by occupying the robber’s vertex if that’s possible. You can put a cop on each vertex and win, so it’s a natural question to ask for the minimum number of cops needed to win. This is the cop number of G, and much research focuses on computing it for various graphs.

Here’s a video in the PBS Infinite Series introducing Cops and Robbers and cop number:

There are many, many variants of the game. For example, the robber may be invisible, only one cop can move at a time, or the cops can capture the robber from a distance. Even with all these variations, the classical version described of Cops and Robbers above is the one most commonly considered.

Beginnings

As it sometimes happens in mathematics, you can trace the origins of Cops and Robbers to a few sources. The first references to the game of Cops and Robbers played on graphs are the following, which are usually cited together:

R. Nowakowski, P. Winkler, Vertex to vertex pursuit in a graph, Discrete Mathematics 43 (1983) 230–239.

A. Quilliot, Jeux et pointes fixes sur les graphes, Thèse de 3ème cycle, Université de Paris VI, 1978, 131–145.

The second reference came first but was a thesis written in French well before the advent of the internet, so it remained less accessible. Both sources independently discovered the result characterizing cop-win graphs, where one cop can win. The cop number came after this in a 1984 paper of Aigner and Fromme, but it is commonly accepted that this paper and thesis were the first time where Cops and Robbers appears.

Not so fast

My ex-post-doc, Benjamin Reiniger, recently discovered a reference to Cops and Robbers found in a book of puzzles Amusements in Mathematics, published in 1917 by Henry Ernest Dudeney. The book contains hundreds of recreational math puzzles, and problem 395, A War Puzzle Game, is of particular interest.

Here is the problem, which begins with the following figure:

“Here is another puzzle game. One player, representing the British general, places a counter at B, and the other player, representing the enemy, places his counter at E. The Britisher makes the first advance along one of the roads to the next town, then the enemy moves to one of his nearest towns, and so on in turns, until the British general gets into the same town as the enemy and captures him. Although each must always move along a road to the next town only, and the second player may do his utmost to avoid capture, the British general (as we should suppose, from the analogy of real life) must infallibly win. But how? That is the question.”

Here, the cop is the Britisher and the robber is enemy. After some reflection, we can see that the graph above is not cop-win, so the initial positions of B and E matter if B is to win.

This is indeed the first historical reference to Cops and Robbers that we know, appearing sixty years before the sources cited above. We should cite this book and problem in all future papers on Cops and Robbers!

An open question on planar graphs

The graph pictured in Dudeney’s puzzle book is an example of a planar graph, which is one that can be drawn on paper without edge crossings (the edges can only touch at vertices). For planar graphs, a theorem of Aigner and Fromme from 1984 tells us that their cop number is at most three. It has an elementary but non-trivial proof, and you can find a readable proof in my book with Nowakowski.

An interesting variant of Cops and Robbers is to slow down the cops so only one of them can move in each round. This variant is akin to chess or checkers. The corresponding parameter for the game is the lazy cop number.  Since we are reducing the power of the cops, the lazy cop number may be larger than the cop number.

An open problem is to find a bound on the lazy cop number of planar graphs. A recent forty page paper of Gao and Yang gives examples of planar graphs whose lazy cop number is at least four.

Anthony Bonato