  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\'{i}l (2009)
and Gaven\v{c}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{\vert V(G) \vert}{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.
