Connected tree-width and connected cops and robber game - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Connected tree-width and connected cops and robber game

Christophe Paul

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : lirmm-02079017 , version 1

Citer

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 Consultations
48 Téléchargements

Partager

Gmail Facebook X LinkedIn More