Cop number

Short description: Number of cops needed to catch a robber on a graph

In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the minimum number of cops that suffices to ensure a win (i.e., a capture of the robber) in a certain pursuit–evasion game on the graph.

Rules

In this game, one player controls the position of a given number of cops and the other player controls the position of a robber. The cops are trying to catch the robber by moving to the same position, while the robber is trying to remain uncaught. Thus, the players perform the following actions, taking turns with each other:

• On the first turn of the game, the player controlling the cops places each cop on a vertex of the graph (allowing more than one cop to be placed on the same vertex).
• Next, the player controlling the robber places the robber on a vertex of the graph.
• On each subsequent turn, the player controlling the cops chooses a (possibly empty) subset of the cops, and moves each of these cops to adjacent vertices. The remaining cops (if any) stay put.
• On the robber's turn, he may either move to an adjacent vertex or stay put.

The game ends with a win for the cops whenever the robber occupies the same vertex as a cop. If this never happens, the robber wins.

The cop number of a graph [math]\displaystyle{ G }[/math] is the minimum number [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ k }[/math] cops can win the game on [math]\displaystyle{ G }[/math].

Example

On a tree, the cop number is one. The cop can start anywhere, and at each step move to the unique neighbor that is closer to the robber. Each of the cop's steps reduces the size of the subtree that the robber is confined to, so the game eventually ends.

By gradually moving closer together, two cops can eventually catch a robber on any cycle (here, a baseball diamond)

On a cycle graph of length more than three, the cop number is two. If there is only one cop, the robber can move to a position two steps away from the cop, and always maintain the same distance after each move of the robber. In this way, the robber can evade capture forever. However, if there are two cops, one can stay at one vertex and cause the robber and the other cop to play in the remaining path. If the other cop follows the tree strategy, the robber will eventually lose.

General results

Every graph whose girth is greater than four has cop number at least equal to its minimum degree. It follows that there exist graphs of arbitrarily high cop number.

Unsolved problem in mathematics: What is the largest possible cop number of an [math]\displaystyle{ n }[/math]-vertex graph? (more unsolved problems in mathematics)

Henri Meyniel (also known for Meyniel graphs) conjectured in 1985 that every connected [math]\displaystyle{ n }[/math]-vertex graph has cop number [math]\displaystyle{ O(\sqrt n) }[/math]. The Levi graphs (or incidence graphs) of finite projective planes have girth six and minimum degree [math]\displaystyle{ \Omega(\sqrt n) }[/math], so if true this bound would be the best possible.

All graphs have sublinear cop number. One way to prove this is to use subgraphs that are guardable by a single cop: the cop can move to track the robber in such a way that, if the robber ever moves into the subgraph, the cop can immediately capture the robber. Two types of subgraph that are guardable are the closed neighborhood of a single vertex, and a shortest path between any two vertices. The Moore bound in the degree diameter problem implies that at least one of these two kinds of guardable sets has size [math]\displaystyle{ \Omega(\log n/\log\log n) }[/math]. Using one cop to guard this set and recursing within the connected components of the remaining vertices of the graph shows that the cop number is at most [math]\displaystyle{ O(n\log\log n/\log n) }[/math].

A more strongly sublinear upper bound on the cop number,

[math]\displaystyle{ \frac{n}{2^{(1-o(1))\sqrt{\log n}}}, }[/math]

is known. However, the problems of obtaining a tight bound, and of proving or disproving Meyniel's conjecture, remain unsolved. It is even unknown whether the soft Meyniel conjecture, that there exists a constant [math]\displaystyle{ c\lt 1 }[/math] for which the cop number is always [math]\displaystyle{ O(n^c) }[/math], is true.

Computing the cop number of a given graph is EXPTIME-hard, and hard for parameterized complexity.

Special classes of graphs

The cop-win graphs are the graphs with cop number equal to one.

Every planar graph has cop number at most three. More generally, every graph has cop number at most proportional to its genus. However, the best known lower bound for the cop number in terms of the genus is approximately the square root of the genus, which is far from the upper bound when the genus is large.

The treewidth of a graph can also be obtained as the result of a pursuit-evasion game, but one in which the robber can move along arbitrary-length paths instead of a single edge in each turn. This extra freedom means that the cop number is generally smaller than the treewidth. More specifically, on graphs of treewidth [math]\displaystyle{ w }[/math], the cop number is at most [math]\displaystyle{ \lfloor w/2\rfloor+1 }[/math].