A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
OPEN ACCESS
Loading...
Author / Producer
Date
2017
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Volume
80
Pages / Article No.
82
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
cops and robbers; capture time; lower bound
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)