Document Open Access Logo

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

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2017.82.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • cops and robbers
  • capture time
  • lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Sebastian Brandt, Yuval Emek, Jara Uitto, and Roger Wattenhofer. A Tight Lower Bound for the Capture Time of the Cops and Robbers Game. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 82:1-82:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.82

Author Details

Sebastian Brandt
Yuval Emek
Jara Uitto
Roger Wattenhofer

References

  1. I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar. Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. In Proccedings of the 46th ACM Symposium on Theory of Computing, STOC, pages 79-88, 2014. Google Scholar
  2. M. Aigner and M. Fromme. A Game of Cops and Robbers. Discrete Applied Mathematics, 8(1):1-12, 1984. URL: http://dx.doi.org/10.1016/0166-218X(84)90073-8.
  3. B. Alspach. Searching and Sweeping Graphs: a Brief Survey. Le Matematiche, 59:5-37, 2006. Google Scholar
  4. T. Andreae. On a pursuit game played on graphs for which a minor is excluded. Journal of Combinatorial Theory, Series B, 41(1):37-47, 1986. Google Scholar
  5. A. Berarducci and B. Intrigila. On the Cop Number of a Graph. Advances in Applied Mathematics, 14(4):389-403, 1993. URL: http://dx.doi.org/10.1006/aama.1993.1019.
  6. A. Bonato and W. Baird. Meyniel’s Conjecture on the Cop Number: a Survey. Journal of Combinatorics, 3:225-238, 2012. Google Scholar
  7. A. Bonato, P. A. Golovach, G. Hahn, and J. Kratochvíl. The Capture Time of a Graph. Discrete Mathematics, 309(18):5588-5595, 2009. URL: http://dx.doi.org/10.1016/j.disc.2008.04.004.
  8. A. Bonato, P. Gordinowicz, B. Kinnersley, and P. Pralat. The Capture Time of the Hypercube. Electr. J. Comb., 20(2):P24, 2013. Google Scholar
  9. A. Bonato and R. J. Nowakowski. The Game of Cops and Robbers on Graphs, volume 61 of Student Mathematical Library. American Mathematical Society, Providence, RI, 2011. Google Scholar
  10. A. Bonato and B. Yang. Graph Searching and Related Problems. In Handbook of Combinatorial Optimization, pages 1511-1558. Springer New York, 2013. URL: http://dx.doi.org/10.1007/978-1-4419-7997-1_76.
  11. N. E. Clarke and G. MacGillivray. Characterizations of k-copwin Graphs. Discrete Mathematics, 312(8):1421-1425, 2012. URL: http://dx.doi.org/10.1016/j.disc.2012.01.002.
  12. F. V. Fomin and D. M. Thilikos. An Annotated Bibliography on Guaranteed Graph Searching. Theor. Comput. Sci., 399(3):236-245, 2008. Google Scholar
  13. K.-T. Förster, R. Nuridini, J. Uitto, and R. Wattenhofer. Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond. In 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 342-356, 2015. Google Scholar
  14. P. Frankl. Cops and Robbers in Graphs with Large Girth and Cayley Graphs. Discrete Appl. Math., 17(3):301-305, June 1987. URL: http://dx.doi.org/10.1016/0166-218X(87)90033-3.
  15. G. Hahn. Cops, Robbers and Graphs. Tatra Mt. Math. Publ, 36(163):163-176, 2007. Google Scholar
  16. A. Kehagias and P. Pralat. Some Remarks on Cops and Drunk Robbers. Theoretical Computer Science, 463:133-147, 2012. Google Scholar
  17. L. Lu and X. Peng. On Meyniel’s Conjecture of the Cop Number. Journal of Graph Theory, 71(2):192-205, 2012. URL: http://dx.doi.org/10.1002/jgt.20642.
  18. A. Mehrabian. The Capture Time of Grids. Discrete Mathematics, 311(1):102-105, 2011. URL: http://dx.doi.org/10.1016/j.disc.2010.10.002.
  19. R. J. Nowakowski and P. Winkler. Vertex-to-vertex Pursuit in a Graph. Discrete Mathematics, 43(2-3):235-239, 1983. URL: http://dx.doi.org/10.1016/0012-365X(83)90160-7.
  20. P. Pralat. When Does a Random Graph Have a Constant Cop Number. Australasian Journal of Combinatorics, 46:285-296, 2010. Google Scholar
  21. A. Quilliot. Jeux et Pointes Fixes sur les Graphes. PhD thesis, Universite de Paris VI, 1978. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact