Document Open Access Logo

Fine-grained Lower Bounds on Cops and Robbers

Authors Sebastian Brandt, Seth Pettie, Jara Uitto

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.9.pdf
  • Filesize: 0.58 MB
  • 12 pages

Document Identifiers

Author Details

Sebastian Brandt
  • ETH Zürich, Zürich, Switzerland
Seth Pettie
  • University of Michigan, Ann Arbor, MI, USA
Jara Uitto
  • ETH Zürich, Zürich, Switzerland

Funding

  • Pettie, Seth: Supported by NSF grants CCF-1514383 and CCF-1637546.
  • Uitto, Jara: Partially supported by ERC Grant No. 336495 (ACDC).

Cite AsGet BibTex

Sebastian Brandt, Seth Pettie, and Jara Uitto. Fine-grained Lower Bounds on Cops and Robbers. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.9

Abstract

Cops and Robbers is a classic pursuit-evasion game played between a group of g cops and one robber on an undirected N-vertex graph G. We prove that the complexity of deciding the winner in the game under optimal play requires Omega (N^{g-o(1)}) time on instances with O(N log^2 N) edges, conditioned on the Strong Exponential Time Hypothesis. Moreover, the problem of calculating the minimum number of cops needed to win the game is 2^{Omega (sqrt{N})}, conditioned on the weaker Exponential Time Hypothesis. Our conditional lower bound comes very close to a conditional upper bound: if Meyniel's conjecture holds then the cop number can be decided in 2^{O(sqrt{N}log N)} time. In recent years, the Strong Exponential Time Hypothesis has been used to obtain many lower bounds on classic combinatorial problems, such as graph diameter, LCS, EDIT-DISTANCE, and REGEXP matching. To our knowledge, these are the first conditional (S)ETH-hard lower bounds on a strategic game.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Cops and Robbers

Metrics

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

References

  1. Akeo Adachi, Shigeki Iwata, and Takumi Kasai. Some combinatorial game problems require ω(n^k) time. J. ACM, 31(2):361-376, 1984. Google Scholar
  2. Martin Aigner and Michael Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8:1-12, 1984. Google Scholar
  3. A. Backurs and P. Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings 47th Annual ACM Symposium on Theory of Computing (STOC), pages 51-58, 2015. Google Scholar
  4. Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 457-466, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.56.
  5. A. Berarducci and B. Intrigila. On the cop number of a graph. Advances in Applied Mathematics, 14(4):389-403, 1993. Google Scholar
  6. Anthony Bonato and Ehsan Chiniforooshan. Pursuit and evasion from a distance: Algorithms and bounds. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics (ANALCO), pages 1-10, 2009. Google Scholar
  7. Anthony Bonato and Richard J. Nowakowski. The Game of Cops and Robbers on Graphs, volume 61. American Mathematical Soc., 2011. Google Scholar
  8. 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), Warsaw, Poland, 2017. Google Scholar
  9. K. Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 661-670, 2014. Google Scholar
  10. K. Bringmann and M. Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 79-97, 2015. Google Scholar
  11. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 307-318, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.36.
  12. W. G. Brown. On graphs that do not contain a Thomsen graph. Canad. Math. Bull., 9:281-285, 1966. Google Scholar
  13. P. L. Chebyshev. Memoire sur les nombres premiers. J. Math. Pures Appl., 17:366-390, 1852. Google Scholar
  14. Nancy E. Clarke and Gary 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.
  15. P. Erdős, A. Rényi, and V. T. Sós. On a problem of graph theory. Studia Sci. Math. Hungar., 1:215-235, 1966. Google Scholar
  16. Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, and Karol Suchan. Pursuing a fast robber on a graph. Theoretical Computer Science, 411(7):1167-1181, 2010. Google Scholar
  17. Peter Frankl. Cops and robbers in graphs with large girth and Cayley graphs. Discrete Applied Mathematics, 17(3):301-305, 1987. URL: http://dx.doi.org/10.1016/0166-218X(87)90033-3.
  18. Arthur S. Goldstein and Edward M. Reingold. The complexity of pursuit on a graph. Theor. Comput. Sci., 143(1), 1995. Google Scholar
  19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  20. David S. Johnson. The NP-completeness column: An ongoing guide. Journal of Algorithms, 4(4):397-411, 1983. Google Scholar
  21. Takumi Kasai, Akeo Adachi, and Shigeki Iwata. Classes of pebble games and complete problems. SIAM Journal on Computing, 8(4):574-586, 1979. Google Scholar
  22. William B. Kinnersley. Cops and robbers is EXPTIME-complete. Journal of Combinatorial Theory, Series B, 111:201-220, 2015. Google Scholar
  23. William B. Kinnersley. Bounds on the length of a game of cops and robbers. CoRR, abs/1706.08379, 2017. URL: http://arxiv.org/abs/1706.08379.
  24. Linyuan Lu and Xing Peng. On Meyniel’s conjecture of the cop number. Journal of Graph Theory, 71(2):192-205, 2012. Google Scholar
  25. Marcello Mamino. On the computational complexity of a game of cops and robbers. Theoretical Computer Science, 477:48-56, 2013. Google Scholar
  26. Paweł Prałat. When does a random graph have constant cop number? Australasian Journal of Combinatorics, 46:285-296, 2010. Google Scholar
  27. Alain Quilliot. Jeux et Pointes Fixes sur les Graphes. PhD thesis, Université de Paris VI, 1978. Google Scholar
  28. I. Reiman. Über ein Problem von K. Zarankiewicz. Acta. Math. Acad. Sci. Hungary, 9:269-273, 1958. Google Scholar
  29. L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings 45th ACM Symposium on Theory of Computing (STOC), pages 515-524, 2013. Google Scholar
  30. Alex Scott and Benny Sudakov. A bound for the cops and robbers problem. SIAM Journal on Discrete Mathematics, 25(3):1438-1442, 2011. URL: http://dx.doi.org/10.1137/100812963.
  31. Larry J. Stockmeyer and Ashok K. Chandra. Provably difficult combinatorial games. SIAM Journal on Computing, 8(2):151-174, 1979. Google Scholar
  32. J. Tits. Sur la trialité et certains groupes qui s'en déduisent. Publ. Math. I.H.E.S., 2:14-20, 1959. Google Scholar
  33. R. Wenger. Extremal graphs with no C^4s, C^6s, or C^10s. J. Comb. Theory Ser. B, 52(1):113-116, 1991. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact