Document Open Access Logo

Recontamination Helps a Lot to Hunt a Rabbit

Authors Thomas Dissaux, Foivos Fioravantes , Harmender Gahlawat , Nicolas Nisse

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.42.pdf
  • Filesize: 0.77 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Dissaux
  • Université Côte d'Azur, Inria, CNRS, I3S, France
Foivos Fioravantes
  • Université Côte d'Azur, Inria, CNRS, I3S, France
  • Department of Theoretical Computer Science, FIT, Czech Technical University in Prague, Czech Republic
Harmender Gahlawat
  • Ben-Gurion University of the Negev, Beersheba, Israel
Nicolas Nisse
  • Université Côte d'Azur, Inria, CNRS, I3S, France

Funding

This research was partially funded by the project UCA JEDI (ANR-15-IDEX-01) and EUR DS4H Investments in the Future (ANR-17-EURE-004) and the ANR Digraphs and the IFCAM project Applications of graph homomorphisms (MA/IFCAM/18/39) and ERC grant titled PARAPATH and the CTU Global postdoc fellowship program.

Cite AsGet BibTex

Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat, and Nicolas Nisse. Recontamination Helps a Lot to Hunt a Rabbit. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.MFCS.2023.42

Abstract

The Hunters and Rabbit game is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number h(G) of a graph G is the minimum integer k such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing h(G) remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the Hunters and Rabbit game imposing that, roughly, a vertex that has already been shot "must not host the rabbit anymore". This allows us to obtain new results in various graph classes. More precisely, let the monotone hunter number mh(G) of a graph G be the minimum integer k such that the Hunter player has a monotone winning strategy. We show that pw(G) ≤ mh(G) ≤ pw(G)+1 for any graph G with pathwidth pw(G), which implies that computing mh(G), or even approximating mh(G) up to an additive constant, is NP-hard. Then, we show that mh(G) can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between h and mh, i.e., that monotonicity does not help. In particular, we show that, for every k ≥ 3, there exists a tree T with h(T) = 2 and mh(T) = k. We conclude by proving that computing h (resp., mh) is FPT parameterised by the minimum size of a vertex cover.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Hunter and Rabbit
  • Monotonicity
  • Graph Searching

Metrics

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

Related Versions

References

  1. T. V. Abramovskaya, F. V. Fomin, P. A. Golovach, and M. Pilipczuk. How to hunt an invisible rabbit on a graph. European Journal of Combinatorics, 52:12-26, 2016. Google Scholar
  2. I. Adler. Marshals, monotone marshals, and hypertree-width. Journal of Graph Theory, 47(4):275-296, 2004. Google Scholar
  3. D. Bienstock and P. D. Seymour. Monotonicity in graph searching. Journal of Algorithms, 12(2):239-245, 1991. Google Scholar
  4. H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms, 18(2):238-255, 1995. Google Scholar
  5. J. Bolkema and C. Groothuis. Hunting rabbits on the hypercube. Discrete Mathematics, 342(2):360-372, 2019. Google Scholar
  6. R. L. Breisch. An intuitive approach to speleotopology. Southwestern cavers, 6(5):72-78, 1967. Google Scholar
  7. J. R. Britnell and M. Wildon. Finding a princess in a palace: a pursuit-evasion problem. The Electronic Journal of Combinatorics, 20(1):25, 2013. Google Scholar
  8. M. Chapelle, M. Liedloff, I. Todinca, and Y. Villanger. Treewidth and pathwidth parameterized by the vertex cover number. Discrete Applied Mathematics, 216:114-129, 2017. Google Scholar
  9. T. 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
  10. D. G. Corneil, Y. Perl, and L. K. Stewart. A linear recognition algorithm for cographs. SIAM Journal on Computing, 14(4):926-934, 1985. Google Scholar
  11. 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
  12. T. Dissaux, F. Fioravantes, H. Galhawat, and N. Nisse. Further results on the Hunters and Rabbit game through monotonicity. Technical report, Inria - Sophia Antipolis, February 2023. URL: https://hal.science/hal-03995642.
  13. 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
  14. H. Gahlawat and M. Zehavi. Parameterized analysis of the cops and robber game. 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 47:1-40:15, Dagstuhl, Germany, 2023. Google Scholar
  15. A. C. Giannopoulou, P. Hunter, and D. M. Thilikos. Lifo-search: A min-max theorem and a searching game for cycle-rank and treedepth. Discrete Applied Mathematics, 160(15):2089-2097, 2012. Google Scholar
  16. 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
  17. V. Gruslys and A. Méroueh. Catching a mouse on a tree. arXiv preprint, 2015. URL: https://arxiv.org/abs/1502.06591.
  18. P. L. Hammer and B. Simeone. The splittance of a graph. Combinatorica, 1:275-284, 1981. Google Scholar
  19. J. Haslegrave. An evasion game on a graph. Discrete Mathematics, 314:1-5, 2014. Google Scholar
  20. D. Ilcinkas, N. Nisse, and D. Soguet. The cost of monotonicity in distributed graph searching. Distributed Computing, 22(2):117-127, 2009. Google Scholar
  21. 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
  22. T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas. Directed tree-width. Journal of Combinatorial Theory Series B, 82(1):138-154, 2001. Google Scholar
  23. A. S. LaPaugh. Recontamination does not help to search a graph. Journal of the ACM, 40(2):224-245, 1993. Google Scholar
  24. F. Mazoit and N. Nisse. Monotonicity of non-deterministic graph searching. Theoretical Computer Science, 399(3):169-178, 2008. Google Scholar
  25. N. Nisse. Network decontamination. In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, 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
  26. T. D. Parsons. Pursuit-evasion in a graph. In Theory and Applications of Graphs, LNCS, volume 642, pages 426-441. Springer, 1978. Google Scholar
  27. 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
  28. 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.
  29. B. Yang, D. Dyer, and B. Alspach. Sweeping graphs with large clique number. Discrete Mathematics, 309(18):5770-5780, 2009. 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