Bounds on the length of a game of cops and robbers

DOI10.1016/J.DISC.2018.05.025MaRDI QIDQ724868zbMATH OpenOpenAlexWikidataFDO

Authors William B. Kinnersley

Publication date 26 July 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.08379

zbMATH Keywords

cops and robberscapture timemoving target searchvertex-pursit games

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

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'{i}l (2009) and Gavenv{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 $kge2$: for fixed $kge2$, we construct arbitrarily large graphs $G$ having capture time at least $left(fracvertV(G)vert40k^{4}ight{)}^{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.

Recommendations

• A tight lower bound for the capture time of the cops and robbers game
• A tight lower bound for the capture time of the cops and robbers game
• The capture time of a graph
• Cop-win graphs with maximum capture-time
• Variations on cops and robbers

Cites work

• A game of cops and robbers
• A tight lower bound for the capture time of the cops and robbers game
• Cop-win graphs with maximum capture-time
• Cops and Robbers on Planar‐Directed Graphs
• Cops and robbers is EXPTIME-complete
• Lower bounds for the capture time: linear, quadratic, and beyond
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• On the computational complexity of a game of cops and robbers
• On the cop number of a graph
• The capture time of a graph
• The capture time of grids
• The capture time of the hypercube
• The complexity of pursuit on a graph
• The game of cops and robbers on graphs
• The game of overprescribed Cops and Robbers played on graphs
• Variations on cops and robbers
• Vertex-to-vertex pursuit in a graph

Cited in

(25)

• Cops and robber on oriented graphs with respect to push operation
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• The localization capture time of a graph
• A tight lower bound for the capture time of the cops and robbers game
• The capture time of a graph
• Throttling for the game of cops and robbers on graphs
• A cops and robber game and the meeting time of synchronous directed walks
• Simultaneously moving cops and robbers
• Capture times in the bridge-burning cops and robbers game
• Fine-grained Lower Bounds on Cops and Robbers
• A cops and robber game in multidimensional grids
• The capture time of grids
• Capture-time extremal cop-win graphs
• Cop-win graphs with maximum capture-time
• Lower bounds for the capture time: linear, quadratic, and beyond
• The capture time of the hypercube
• A faster algorithm for cops and robbers
• Jumping robbers in digraphs
• A tight lower bound for the capture time of the cops and robbers game
• Cops and Robbers on diameter two graphs
• Variations on cops and robbers
• Cops and robber on some families of oriented graphs
• The game of overprescribed Cops and Robbers played on graphs
• Time-delayed cops and robbers
• Optimizing the trade-off between number of cops and capture time in cops and robbers

This page was built for publication: Bounds on the length of a game of cops and robbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724868)