Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor

Authors Prosenjit Bose, Jean-Lou De Carufel, Thomas Shermer



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.56.pdf
  • Filesize: 0.82 MB
  • 13 pages

Document Identifiers

Author Details

Prosenjit Bose
  • School of Computer Science, Carleton University, Ottawa, Canada
Jean-Lou De Carufel
  • School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada
Thomas Shermer
  • School of Computing Science, Simon Fraser University, Burnaby, Canada

Acknowledgements

P. Bose would like to thank P. Morin for fruitful discussions on various aspects of structural graph theory and for bringing reference [D. Harvey and D. Wood, 2017] to his attention.

Cite AsGet BibTex

Prosenjit Bose, Jean-Lou De Carufel, and Thomas Shermer. Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 56:1-56:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.56

Abstract

We study zombies and survivor, a variant of the game of cops and robber on graphs. In this variant, the single survivor plays the role of the robber and attempts to escape from the zombies that play the role of the cops. The zombies are restricted, on their turn, to always follow an edge of a shortest path towards the survivor. Let z(G) be the smallest number of zombies required to catch the survivor on a graph G with n vertices. We show that there exist outerplanar graphs and visibility graphs of simple polygons such that z(G) = Θ(n). We also show that there exist maximum-degree-3 outerplanar graphs such that z(G) = Ω(n/log(n)). Let z_L(G) be the smallest number of lazy zombies (zombies that can stay still on their turn) required to catch the survivor on a graph G. We show that lazy zombies are more powerful than normal zombies but less powerful than cops. We prove that z_L(G) ≤ 2 for connected outerplanar graphs and this bound is tight in the worst case. We show that z_L(G) ≤ k for connected graphs with treedepth k. This result implies that z_L(G) is at most (k+1)log n for connected graphs with treewidth k, O(√n) for connected planar graphs, O(√{gn}) for connected graphs with genus g and O(h√{hn}) for connected graphs with any excluded h-vertex minor. Our results on lazy zombies still hold when an adversary chooses the initial positions of the zombies.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Pursuit-evasion games
  • Outerplanar
  • Graphs
  • Treedepth
  • Treewidth

Metrics

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

References

  1. M. Aigner and M. Fromme. A game of cops and robbers. Discret. Appl. Math., 8(1):1-12, 1984. Google Scholar
  2. N. Alon, P. Seymour, and R. Thomas. A separator theorem for graphs with an excluded minor and its applications. In H. Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 293-299. ACM, 1990. Google Scholar
  3. T. Andreae. On a pursuit game played on graphs for which a minor is excluded. J. Comb. Theory, Ser. B, 41(1):37-47, 1986. Google Scholar
  4. V. Bartier, L. Bénéteau, M. Bonamy, H. La, and J. Narboni. A note on deterministic zombies. Discret. Appl. Math., 301:65-68, 2021. Google Scholar
  5. H. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1-45, 1998. Google Scholar
  6. A. Bonato and R. Nowakowski. The Game of Cops and Robbers on Graphs. AMS, 2011. Google Scholar
  7. P. Bose, J.-L. De Carufel, and T. Shermer. Pursuit-evasion in graphs: Zombies, lazy zombies and a survivor. CoRR, abs/2204.11926, 2022. URL: http://arxiv.org/abs/2204.11926.
  8. H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, May 2005. Google Scholar
  9. N. Clarke. Constrained cops and robber. PhD thesis, Dalhousie University, Halifax, Canada, 2002. Google Scholar
  10. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. Google Scholar
  11. R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  12. Z. Dvorák and S. Norin. Treewidth of graphs with balanced separations. J. Comb. Theory, Ser. B, 137:137-144, 2019. Google Scholar
  13. S. Fitzpatrick, J. Howell, M.-E. Messinger, and D. Pike. A deterministic version of the game of zombies and survivors on graphs. Discret. Appl. Math., 213:1-12, 2016. Google Scholar
  14. J. Gilbert, J. Hutchinson, and R. Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5(3):391-407, 1984. Google Scholar
  15. D. Harvey and D. Wood. Parameters tied to treewidth. J. Graph Theory, 84(4):364-385, 2017. Google Scholar
  16. G. Joret, M. Kaminski, and D. Theis. The cops and robber game on graphs with forbidden (induced) subgraphs. Contributions Discret. Math., 5(2), 2010. Google Scholar
  17. R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. Google Scholar
  18. T. Lozano-Pérez and M. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, 22(10):560-570, 1979. Google Scholar
  19. J. Nesetril and P. Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  20. R. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a graph. Discret. Math., 43(2-3):235-239, 1983. Google Scholar
  21. A. Quilliot. Jeux et pointes fixes sur les graphes. PhD thesis, Université de Paris VI, Paris, France, 1978. Google Scholar
  22. N. Robertson and P. Seymour. Graph minors. II. algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986. Google Scholar
  23. B. Schröder. The copnumber of a graph is bounded by [3/2 genus (g)] + 3. In J. Koslowski and A. Melton, editors, Categorical Perspectives, pages 243-263, Boston, MA, 2001. Birkhäuser Boston. 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