License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.82
URN: urn:nbn:de:0030-drops-74134
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7413/
Go to the corresponding LIPIcs Volume Portal

Brandt, Sebastian ; Emek, Yuval ; Uitto, Jara ; Wattenhofer, Roger

A Tight Lower Bound for the Capture Time of the Cops and Robbers Game

pdf-format:
LIPIcs-ICALP-2017-82.pdf (0.6 MB)

Abstract

For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O(n^{k + 1}), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. In this paper, the question of Bonato and Nowakowski is answered on the negative, proving that the O(n^{k + 1}) bound is asymptotically tight for any constant k >= 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.

BibTeX - Entry

@InProceedings{brandt_et_al:LIPIcs:2017:7413,
  author =	{Sebastian Brandt and Yuval Emek and Jara Uitto and Roger Wattenhofer},
  title =	{{A Tight Lower Bound for the Capture Time of the Cops and Robbers Game}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{82:1--82:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7413},
  URN =		{urn:nbn:de:0030-drops-74134},
  doi =		{10.4230/LIPIcs.ICALP.2017.82},
  annote =	{Keywords: cops and robbers, capture time, lower bound}
}

Keywords: cops and robbers, capture time, lower bound
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI