License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.7
URN: urn:nbn:de:0030-drops-115695
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11569/
Go to the corresponding LIPIcs Volume Portal


Adler, Isolde ; Paul, Christophe ; Thilikos, Dimitrios M.

Connected Search for a Lazy Robber

pdf-format:
LIPIcs-FSTTCS-2019-7.pdf (0.8 MB)


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.

BibTeX - Entry

@InProceedings{adler_et_al:LIPIcs:2019:11569,
  author =	{Isolde Adler and Christophe Paul and Dimitrios M. Thilikos},
  title =	{{Connected Search for a Lazy Robber}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11569},
  URN =		{urn:nbn:de:0030-drops-115695},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.7},
  annote =	{Keywords: Graph searching, Tree-decomposition, Obstructions}
}

Keywords: Graph searching, Tree-decomposition, Obstructions
Seminar: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 10.12.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI