Document Open Access Logo

Parameterized Analysis of the Cops and Robber Game

Authors Harmender Gahlawat , Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.49.pdf
  • Filesize: 0.91 MB
  • 17 pages

Document Identifiers

Author Details

Harmender Gahlawat
  • Ben-Gurion University of the Negev, Beersheba, Israel
Meirav Zehavi
  • Ben-Gurion University of the Negev, Beersheba, Israel

Funding

This research was supported by the European Research Council (ERC) grant titled PARAPATH.

Cite AsGet BibTex

Harmender Gahlawat and Meirav Zehavi. Parameterized Analysis of the Cops and Robber Game. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 49:1-49:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.MFCS.2023.49

Abstract

Pursuit-evasion games have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theory, distributed computing, and algorithmic theory. Cops and Robber (CnR) is one of the most well-known pursuit-evasion games played on graphs, where multiple cops pursue a single robber. The aim is to compute the cop number of a graph, k, which is the minimum number of cops that ensures the capture of the robber. From the viewpoint of parameterized complexity, CnR is W[2]-hard parameterized by k [Fomin et al., TCS, 2010]. Thus, we study structural parameters of the input graph. We begin with the vertex cover number (vcn). First, we establish that k ≤ vcn/3+1. Second, we prove that CnR parameterized by vcn is FPT by designing an exponential kernel. We complement this result by showing that it is unlikely for CnR parameterized by vcn to admit a polynomial compression. We extend our exponential kernels to the parameters cluster vertex deletion number and deletion to stars number, and design a linear vertex kernel for neighborhood diversity. Additionally, we extend all of our results to several well-studied variations of CnR.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Cops and Robber
  • Kernelization
  • Graph Searching
  • Fixed parameter tractability

Metrics

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

Related Versions

References

  1. I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM Journal on Computing, 48(3):1120-1145, 2019. Google Scholar
  2. M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8(1):1-12, 1984. Google Scholar
  3. 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
  4. D. Angelo, A. Navarra, and N. Nisse. A unified approach for gathering and exclusive searching on rings under weak assumptions. Distributed Computing, 30:17-48, 2017. Google Scholar
  5. J. A. Baier, A. Botea, D. Harabor, and C. Hernández. Fast algorithm for catching a prey quickly in known and partially known game maps. IEEE Transactions on Computational Intelligence and AI in Games, 7(2):193-199, 2015. URL: https://doi.org/10.1109/TCIAIG.2014.2337889.
  6. A. Berarducci and B. Intrigila. On the cop number of a graph. Advances in Applied mathematics, 14(4):389-403, 1993. Google Scholar
  7. A. Beveridge, A. Dudek, A. Frieze, and T. Müller. Cops and robbers on geometric graphs. Combinatorics, Probability and Computing, 21(6):816-834, 2012. Google Scholar
  8. A. Bonato, S. Finbow, P. Gordinowicz, A. Haidar, W. B. Kinnersley, D. Mitsche, P. Prałat, and L. Stacho. The robber strikes back. In proceedings of Computational Intelligence, Cyber Security and Computational Models, volume 246, pages 3-12. Springer, 2014. Google Scholar
  9. A. Bonato and R. Nowakowski. The Game of Cops and Robbers on Graphs. American Mathematical Society, 2011. Google Scholar
  10. E. Bonnet, S. Gaspers, A. Lambilliotte, S. Rümmele, and A. Saffidine. The parameterized complexity of positional games. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pages 90:1-90:14, 2017. Google Scholar
  11. E. Bonnet, F. Jamain, and A. Saffidine. On the complexity of connection games. Theoretical Computer Science, 644:2-28, 2016. Google Scholar
  12. N. Bowler, J. Erde, F. Lehner, and M. Pitz. Bounding the cop number of a graph by its genus. SIAM Journal on Discrete Mathematics, 35(4):2459-2489, 2021. Google Scholar
  13. P. Bradshaw, S. A. Hosseini, and J. Turcotte. Cops and robbers on directed and undirected abelian Cayley graphs. European Journal of Combinatorics, 97, 2021. Google Scholar
  14. S. Brandt, S. Pettie, and S. Uitto. Fine-grained lower bounds on cops and robbers. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.9.
  15. A. C. Burgess, R. A. Cameron, N. E. Clarke, P. Danziger, S. Finbow, C. W. Jones, and D. A. Pike. Cops that surround a robber. Discrete Applied Mathematics, 285:552-566, 2020. Google Scholar
  16. T. H. Chung, G. A. Hollinger, and V. Isler. Search and pursuit-evasion in mobile robotics: A survey. Autonomous Robots, 31(299):299-316, 2011. Google Scholar
  17. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition, 2015. Google Scholar
  18. J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak. Evacuating robots via unknown exit in a disk. In F. Kuhn, editor, Distributed Computing (DISC 2014), volume 8784 of Lecture Notes in Computer Science, pages 122-136, 2018. URL: https://doi.org/10.1007/978-3-662-45174-8_9.
  19. S. Das and H. Gahlawat. Variations of cops and robbers game on grids. Discrete Applied Mathematics, 305:340-349, 2021. Google Scholar
  20. S. Das and H. Gahlawat. On the Cop Number of String Graphs. In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1-45:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2022.45.
  21. S. Das, H. Gahlawat, U. k. Sahoo, and S. Sen. Cops and robber on some families of oriented graphs. Theoretical Computer Science, 888:31-40, 2021. Google Scholar
  22. T. Dissaux, Fioravantes F., H. Gahlawat, and N. Nicolas. Recontamination helps a lot to hunt a rabbit. In Bérôme Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1-40:14, Dagstuhl, Germany, 2023. Google Scholar
  23. M. Dom, D. Lokshtanov, and S. Saurabh. Incompressibility through colors and ids. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP '09, pages 378-389, Berlin, Heidelberg, 2009. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-02927-1_32.
  24. H. E. Dudeney. Amusements in Mathematics. Facsimile Publisher, 1917. Google Scholar
  25. J. A. Ellis, I. H. Sudborough, and J. S. Turner. The vertex separation and search number of a graph. Information and Computation, 113(1):50-79, 1994. Google Scholar
  26. M. R. Fellows. The lost continent of polynomial time: Preprocessing and kernelization. In Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, IWPEC'06, pages 276-277, Berlin, Heidelberg, 2006. Springer-Verlag. URL: https://doi.org/10.1007/11847250_25.
  27. F. Fomin, P. Golovach, J. Kratochvíl, N. Nisse, and K. Suchan. Pursuing a fast robber on a graph. Theoretical Computer Science, 41(7-9):1167-1181, 2010. Google Scholar
  28. F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  29. H. Gahlawat and M. Zehavi. Parameterized analysis of the cops and robber problem. arXiv:2307.04594, 2023. URL: https://doi.org/10.48550/arXiv.2307.04594.
  30. N. Galesi, N. Talebanfard, and J. Torán. Cops-robber games and the resolution of tseitin formulas. ACM Transactions on Computation Theory, 12(2):1-22, 2020. Google Scholar
  31. G. Gottlob, N. Leone, and F. Scarcello. A comparison of structural csp decomposition methods. Artificial Intelligence, 124(2):243-282, 2000. Google Scholar
  32. G. Gottlob, N. Leone, and F. Scarcello. The complexity of acyclic conjunctive queries. Journal of the ACM, 48(3):431-498, 2001. Google Scholar
  33. G. Gottlob, N. Leone, and F. Scarcello. Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. Journal of Computer and System Sciences, 66(4):775-808, 2003. Google Scholar
  34. I. Gromovikov, W. B. Kinnersleyb, and B. Seamone. Fully active cops and robbers. Australian Journal of Combinatorics, 76(2):248-265, 2020. Google Scholar
  35. R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. John Wiley and Sons, New York, 1965. Google Scholar
  36. A. Isaza, J. Lu, V. Bulitko, and R. Greiner. A cover-based approach to multi-agent moving target pursuit. In proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, pages 54-59. AAAI Press, 2008. Google Scholar
  37. T. Ishida and R. E. Korf. Moving target search. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, IJCAI'91, pages 204-210, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc. Google Scholar
  38. G. Joret, M. Kaminski, and D. O. Theis. Cops and robber game on graphs with forbidden (induced) subgraphs. Contributions to Discrete Mathematics, 5(2):40-51, 2010. Google Scholar
  39. W. B. Kinnersley. Cops and robbers is exptime-complete. Journal of Combinatorial Theory Series B, 111:201-220, 2015. Google Scholar
  40. K. Klein and S. Suri. Catch me if you can: Pursuit and capture in polygonal environments with obstacles. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2012), volume 26, pages 2010-2016, 2012. URL: https://doi.org/DOI:10.1609/aaai.v26i1.8375.
  41. F. Lehner. On the cop number of toroidal graphs. Journal of Combinatorial Theory, Series B, 151:250-262, 2021. Google Scholar
  42. P. Loh and S. Oh. Cops and robbers on planar directed graphs. Journal of Graph Theory, 86(3):329-340, 2017. Google Scholar
  43. M. Mamino. On the computational complexity of a game of cops and robbers. Theoretical Computer Science, 477:48-56, 2013. Google Scholar
  44. C. Moldenhauer and N. R. Sturtevant. Evaluating strategies for running from the cops. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI'09, pages 584-589, San Francisco, CA, USA, 2009. Morgan Kaufmann Publishers Inc. Google Scholar
  45. N. Nisse. Network decontamination. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 516-548. Springer, 2019. Google Scholar
  46. R. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a graph. Discrete Mathematics, 43(2-3):235-239, 1983. Google Scholar
  47. D. Offner and K. Ojakian. Variations of cops and robber on the hypercube. Australasian Journal of Combinatorics, 59(2):229-250, 2014. Google Scholar
  48. T. D. Parsons. Pursuit-evasion in a graph. In Theory and Applications of Graphs, LNCS, volume 642, pages 426-441. Springer, 1978. Google Scholar
  49. V. Patsko, S. Kumkov, and V. Turova. Pursuit-evasion games. In Handbook of Dynamic Game Theory, pages 951-1038. Springer, 2018. Google Scholar
  50. J. Petr, J. Portier, and L. Versteegen. A faster algorithm for cops and robbers. arXiv, 2021. URL: https://arxiv.org/abs/2112.07449v2.
  51. A. Quilliot. Thése d'Etat. PhD thesis, Université de Paris VI, 1983. Google Scholar
  52. A. Scott. On the Parameterized Complexity of Finding Short Winning Strategies in Combinatorial Games. PhD thesis, University of Victoria, 2009. Google Scholar
  53. A. Scott and U. Stege. Parameterized pursuit-evasion games. Theoretical Computer Science, 411(43):3845-3858, 2010. Google Scholar
  54. P. D. Seymour and R. Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory Series B, 58(1):22-33, 1993. Google Scholar
  55. D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. URL: http://www.cambridge.org/de/knowledge/isbn/item5759340/?site_locale=de_DE.
  56. F. Xie, A. Botea, and A. Kishimoto. A scalable approach to chasing multiple moving targets with multiple agents. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI'17, pages 4470-4476. AAAI Press, 2017. 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