Document Open Access Logo

Connected Search for a Lazy Robber

Authors Isolde Adler, Christophe Paul, Dimitrios M. Thilikos

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.7.pdf
  • Filesize: 0.8 MB
  • 14 pages

Document Identifiers

Author Details

Isolde Adler
  • School of Computing, University of Leeds, Leeds, United Kingdom
Christophe Paul
  • CNRS, LIRMM, Université de Montpellier, Montpellier, France
Dimitrios M. Thilikos
  • CNRS, LIRMM, Université de Montpellier, Montpellier, France

Funding

  • Paul, Christophe: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).
  • Thilikos, Dimitrios M.: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). Supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.

Cite AsGet BibTex

Isolde Adler, Christophe Paul, and Dimitrios M. Thilikos. Connected Search for a Lazy Robber. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.7

Abstract

The node search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search-game analogue of the treewidth parameter (and, respectively, pathwidth). In the connected variants of the above two games, we additionally demand that, at each moment of the search, the clean territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected pathwidth. It is known that the price of connectivty to search for an agile robber is bounded by 2, that is the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth. In this paper, we investigate the connected search game against a lazy robber. A lazy robber moves only when the searchers' strategy threatens the location that he currently occupies. We introduce two alternative graph-theoretic formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of connected treewidth. We observe that connected treewidth parameter is closed under contractions and prove that for every k >= 2, the set of contraction obstructions of the class of graphs with connected treewidth at most k is infinite. Our main result is a complete characterization of the obstruction set for k=2. One may observe that, so far, only a few complete obstruction sets are explicitly known for contraction closed graph classes. We finally show that, in contrast to the agile robber game, the price of connectivity is unbounded.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Graph searching
  • Tree-decomposition
  • Obstructions

Metrics

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

References

  1. Isolde Adler. Open Problems related to computing obstruction sets. Manuscript, September 2008. Google Scholar
  2. Steve Alpern and Shmuel Gal. The theory of search games and rendezvous. International Series in Operations Research & Management Science, 55. Kluwer Academic Publishers, Boston, MA, 2003. Google Scholar
  3. Brian Alspach. Searching and sweeping graphs: a brief survey. Matematiche (Catania), 59(1-2):5-37 (2006), 2004. Google Scholar
  4. Stefan Arnborg, Andrzej Proskurowski, and Derek G. Corneil. Forbidden minors characterization of partial 3-trees. Discrete Mathematics, 80(1):1-19, 1990. Google Scholar
  5. Lali Barrière, Paola Flocchini, Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse, Nicola Santoro, and Dimitrios M. Thilikos. Connected graph searching. Inf. Comput., 219:1-16, 2012. URL: https://doi.org/10.1016/j.ic.2012.08.004.
  6. Lali Barrière, Pierre Fraigniaud, Nicola Santoro, and Dimitrios M. Thilikos. Searching Is Not Jumping. In 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), volume 2880 of LNCS, pages 34-45. Springer, 2003. Google Scholar
  7. Micah J Best, Arvind Gupta, Dimitrios M. Thilikos, and Dimitris Zoros. Contraction obstructions for connected graph searching. Discrete Applied Mathematics, 209:27-47, 2016. 9th International Colloquium on Graph Theory and Combinatorics, 2014, Grenoble. Google Scholar
  8. D. Bienstock and Paul Seymour. Monotonicity in graph searching. J. Algorithms, 12(2):239-245, 1991. Google Scholar
  9. Dan Bienstock, Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a forest. J. Comb. Theory Ser. B, 52(2):274-283, 1991. Google Scholar
  10. Daniel Bienstock. Graph searching, path-width, tree-width and related problems (a survey). In Reliability of computer and communication networks (New Brunswick, NJ, 1989), volume 5 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 33-49. Amer. Math. Soc., Providence, RI, 1991. Google Scholar
  11. R. Breisch. An intuitive approach to speleotopology. Southwestern Cavers (A publication of the Southwestern Region of the National Speleological Society), VI(5):72-78, 1967. Google Scholar
  12. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction. Algorithmica, 54(2):142-180, 2009. URL: https://doi.org/10.1007/s00453-007-9138-y.
  13. Nick D. Dendris, Lefteris M. Kirousis, and Dimitrios M. Thilikos. Fugitive-search games on graphs and related parameters. Theoret. Comput. Sci., 172(1-2):233-254, 1997. Google Scholar
  14. Dariusz Dereniowski. From Pathwidth to Connected Pathwidth. SIAM J. Discrete Math., 26(4):1709-1732, 2012. URL: https://doi.org/10.1137/110826424.
  15. Reinhard Diestel and Malte Müller. Connected Tree-Width. Combinatorica, 38(2):381-398, 2018. URL: https://doi.org/10.1007/s00493-016-3516-5.
  16. Paola Flocchini, Miao Jun Huang, and Flaminia L. Luccio. Contiguous Search in the Hypercube for Capturing an Intruder. In Proceedings of the 19th International Parallel and Distributed Processing Symposium (IPDPS 2005) IPDPS. IEEE Computer Society, 2005. Google Scholar
  17. Paola Flocchini, Miao Jun Huang, and Flaminia L. Luccio. Decontamination of chordal rings and tori using mobile agents. Int. J. of Found. of Comp. Sc., 18(3):547-564, 2007. Google Scholar
  18. Paola Flocchini, Miao Jun Huang, and Flaminia L. Luccio. Decontamination of hypercubes by mobile agents. Networks, page to appear, 2007. Google Scholar
  19. F. V. Fomin, D. M. Thilikos, and I. Todinca. Connected Graph Searching in Outerplanar Graphs. Electronic Notes in Discrete Mathematics, 22:213-216, 2005. 7th International Colloquium on Graph Theory. Short communication. Google Scholar
  20. Fedor V. Fomin and Dimitrios M. Thilikos. On the monotonicity of games generated by symmetric submodular functions. Discrete Appl. Math., 131(2):323-335, 2003. Submodularity. URL: https://doi.org/10.1016/S0166-218X(02)00459-6.
  21. Fedor V. Fomin and Dimitrios M. Thilikos. An annotated bibliography on guaranteed graph searching. Theoret. Comput. Sci., 399(3):236-245, 2008. Google Scholar
  22. Pierre Fraigniaud and Nicolas Nisse. Connected Treewidth and Connected Graph Searching. In Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), volume 3887 of LNCS, pages 479-490. Springer, 2006. Google Scholar
  23. Pierre Fraigniaud and Nicolas Nisse. Connected Treewidth and Connected Graph Searching. In 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), volume 3887 of LNCS, pages 479-490. Springer, 2006. Google Scholar
  24. Pierre Fraigniaud and Nicolas Nisse. Monotony Properties of Connected Visible Graph Searching. In 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), volume 4271 of LNCS, pages 229-240. Springer, 2006. Google Scholar
  25. Matthias Hamann and Daniel Weißauer. Bounding Connected Tree-Width. SIAM J. Discrete Math., 30(3):1391-1400, 2016. URL: https://doi.org/10.1137/15M1044618.
  26. Philippe Jégou and Cyril Terrioux. Bag-Connected Tree-Width: A New Parameter for Graph Decomposition. In International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014, Fort Lauderdale, FL, USA, January 6-8, 2014, 2014. URL: http://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Jegou_Terrioux_New.pdf.
  27. Philippe Jégou and Cyril Terrioux. Tree-Decompositions with Connected Clusters for Solving Constraint Networks. In Barry O'Sullivan, editor, Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings, volume 8656 of Lecture Notes in Computer Science, pages 407-423. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-10428-7_31.
  28. Philippe Jégou and Cyril Terrioux. Combining restarts, nogoods and bag-connected decompositions for solving CSPs. Constraints, 22(2):191-229, 2017. URL: https://doi.org/10.1007/s10601-016-9248-8.
  29. Marcin Kaminski, Daniël Paulusma, and Dimitrios M. Thilikos. Contracting planar graphs to contractions of triangulations. J. Discrete Algorithms, 9(3):299-306, 2011. URL: https://doi.org/10.1016/j.jda.2011.03.010.
  30. Nancy G. Kinnersley and Michael A. Langston. Obstruction set Isolation for the Gate Matrix Layout Problem. Discrete Applied Mathematics, 54:169-213, 1994. Google Scholar
  31. Lefteris M. Kirousis and Christos H. Papadimitriou. Interval graphs and searching. Discrete Math., 55(2):181-184, 1985. Google Scholar
  32. Lefteris M. Kirousis and Christos H. Papadimitriou. Searching and pebbling. Theoret. Comput. Sci., 47(2):205-218, 1986. Google Scholar
  33. J. Lagergren. Upper bounds on the size of obstructions and intertwines. J. Comb. Theory, Ser. B, 73:7-40, 1998. Google Scholar
  34. Andrea S. LaPaugh. Recontamination does not help to search a graph. J. Assoc. Comput. Mach., 40(2):224-245, 1993. Google Scholar
  35. Thomas W. Mattman. Forbidden Minors: Finding the Finite Few. In Aaron Wootton, Valerie Peterson, and Christopher Lee, editors, A Primer for Undergraduate Research: From Groups and Tiles to Frames and Vaccines, pages 85-97, Cham, 2017. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-66065-3_4.
  36. Rolf H. Möhring. Graph problems related to gate matrix layout and PLA folding. In Computational graph theory, volume 7 of Comput. Suppl., pages 17-51. Springer, Vienna, 1990. Google Scholar
  37. Nicolas Nisse. Connected graph searching in chordal graphs. Discrete Applied Mathematics, 157(12):2603-2610, 2009. Second Workshop on Graph Classes, Optimization, and Width Parameters. URL: https://doi.org/10.1016/j.dam.2008.08.007.
  38. Nicolas Nisse. Network Decontamination, pages 516-548. Springer International Publishing, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7_19.
  39. T. D. Parsons. Pursuit-evasion in a graph. In Theory and applications of graphs, volume 642 of Lecture Notes in Math., pages 426-441. Springer, Berlin, 1978. Google Scholar
  40. Neil Robertson and P. D. Seymour. Graph Minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. Google Scholar
  41. Daniel P. Sanders. On linear recognition of tree-width at most four. SIAM J. Discrete Math., 9(1):101-117, 1996. Google Scholar
  42. P. D. Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width. J. Comb. Theory Ser. B, 58(1):22-33, 1993. 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