Connected tree-width and connected cops and robber game - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Connected tree-width and connected cops and robber game

Christophe Paul


The node search game against a lazy/agile invisible robber has been introduced as a search-game analogue of the graph parameters of treewidth/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 path width. It has been shown that its value cannot be more than the double (plus some constant) of its non-connected counterpart. This implied that the "price of connectivity" is bounded by 2 for the case of an agile robber. In this talk, we consider the connected variant of this search game where the robber is lazy. We introduce two alternative graph-theoretical 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 tree width. We first show that in contrast to the "agile-robber" variant, the price of connectivity for the "lazy-robber" game is unbounded. To that aim, we observe that the connected treewidth parameter is closed under contraction and prove that the set of contraction obstruction is infinite for every integer k ≥ 2.
Fichier principal
Vignette du fichier
ChristophePaul-caalm19.pdf (2.87 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-02079017 , version 1 (13-01-2022)


  • HAL Id : lirmm-02079017 , version 1


Christophe Paul. Connected tree-width and connected cops and robber game. CAALM 2019 - Complexity, Algorithms, Automata and Logic Meet, Jan 2019, Chennai, India. ⟨lirmm-02079017⟩
93 View
48 Download


Gmail Facebook X LinkedIn More