License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.56
URN: urn:nbn:de:0030-drops-173418
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17341/
Bose, Prosenjit ;
De Carufel, Jean-Lou ;
Shermer, Thomas
Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor
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.
BibTeX - Entry
@InProceedings{bose_et_al:LIPIcs.ISAAC.2022.56,
author = {Bose, Prosenjit and De Carufel, Jean-Lou and Shermer, Thomas},
title = {{Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {56:1--56:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17341},
URN = {urn:nbn:de:0030-drops-173418},
doi = {10.4230/LIPIcs.ISAAC.2022.56},
annote = {Keywords: Pursuit-evasion games, Outerplanar, Graphs, Treedepth, Treewidth}
}
|
Keywords: |
|
Pursuit-evasion games, Outerplanar, Graphs, Treedepth, Treewidth |
|
Collection: |
|
33rd International Symposium on Algorithms and Computation (ISAAC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
