Finding small-width connected path decompositions in polynomial time

Abstract

A connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\dots ,X_l)$ such that the subgraph of $G$ induced by $X_1\cup \cdots \cup X_i$ is connected for each $i\in \{1,\dots ,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game.

References in corpus (4)

• Connected searching of weighted trees
• From Pathwidth to Connected Pathwidth
• Minimum length path decompositions
• Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings