Bounds on the length of a game of Cops and Robbers

Abstract

In the game of Cops and Robbers, a team of cops attempts to capture a robber on a graph $G$. All players occupy vertices of $G$. The game operates in rounds; in each round the cops move to neighboring vertices, after which the robber does the same. The minimum number of cops needed to guarantee capture of a robber on $G$ is the cop number of $G$, denoted $c(G)$, and the minimum number of rounds needed for them to do so is the capture time. It has long been known that the capture time of an $n$-vertex graph with cop number $k$ is $O(n^{k+1})$. More recently, Bonato, Golovach, Hahn, and Kratochvíl (2009) and Gavenčiak (2010) showed that for $k=1$, this upper bound is not asymptotically tight: for graphs with cop number 1, the cop can always win within $n-4$ rounds. In this paper, we show that the upper bound is tight when $k\ge 2$: for fixed $k\ge 2$, we construct arbitrarily large graphs $G$ having capture time at least ${\left(\frac{|V(G)|}{40k^4}\right)}^{k+1}$. In the process of proving our main result, we establish results that may be of independent interest. In particular, we show that the problem of deciding whether $k$ cops can capture a robber on a directed graph is polynomial-time equivalent to deciding whether $k$ cops can capture a robber on an undirected graph. As a corollary of this fact, we obtain a relatively short proof of a major conjecture of Goldstein and Reingold (1995), which was recently proved through other means by the author (2015). We also show that $n$-vertex strongly-connected directed graphs with cop number 1 can have capture time $\Omega (n^2)$, thereby showing that the result of Bonato et al. does not extend to the directed setting.