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 pathwidth. It has been shown that the value of the connected pathwidth cannot be more than the double (asymptotically) 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 the node search game where the robber is lazy: he/she moves only when the searchers strategy threatens the location that he/she currently occupies. We introduce two alternative graph-theoretical formulations of its monotone variant, one in terms of (connected) layouts and one on terms of (connected) tree decompositions, leading to the graph parameter of connected treewidth. For this “lazy-robber” variant we prove that there is no bound in the price of connectivity, which comes in contrast to the case of an agile robber. We also observe that the corresponding parameter, i.e. connected treewidth, is closed under contractions and we study the contraction-obstruction set class of the class of graphs with connected treewidth at most $k$. It follows that this set is infinite for every $k\geq 2$. We also provide a complete characterisation for the case where $k = 2$.

This is joint work with Isolde Adler (University of Leeds) and Dimitrios M. Thilikos (CNRS, LIRMM).