Bounds on the length of a game of Cops and Robbers

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 (Kinnersley, 2015). We also show that n-vertex strongly-connected directed graphs with cop number 1 can have capture time Ω(n2), thereby showing that the result of Bonato et al. (2009) does not extend to the directed setting.