A new prehistory of Cops and Robbers

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.

Image result for pac man
Pac-Man is an example of a graph searching game that was all the rage back in the 1980’s.

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.

Image result for richard nowakowski math
The inimitable mathematician and gamer Richard Nowakowski.

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.

Image result for planar graphs
The dodecahedron is a planar graph. The cop number of this graph is 3.

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

 

5 thoughts on “A new prehistory of Cops and Robbers

  1. This puzzle has some interesting quirks. It relies on being a doubly-active version (each player has to move each turn), and the graph is bipartite without the top-left triangle, with the cop and robber starting in the same partite set. This means, if neither player ever visits the triangle, that the cop can only win by forcing the robber to move into the cop’s vertex, which can only happen if the robber is silly enough to visit a leaf (and the leaves here are all adjacent to vertices with degree at least 3, so the robber can avoid that). So, for the cop to win, they must switch colors via the triangle and prevent the robber from later also switching.

    Even after that maneuver, the cop has to be able to corner the robber. I don’t see as easy an argument for why that’s possible [Dudeny just says it’s easy to do], but there are several vertices whose closed neighborhoods separate the graph which seems to be quite helpful. Or maybe there’s a reduction from the bipartite graph to a non-active version whose graph is cop-win (or an adaptation of the cop-win characterization for active bipartite games)?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s