From Pathwidth to Connected Pathwidth
Dariusz Dereniowski · SIAM Journal on Discrete Mathematics · 2012
It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\textup{pw}(G)+1$, where $\textup{pw}(G)$ is the pathwidth of $G$. The method is constructive, i.e., it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$, where $d$ is the number of “bags” in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality $\textup{\texttt{cs}}(G)\leq 2\textup{\texttt{s}}(G)+3$, where $\textup{\texttt{cs}}(G)$ and $\textup{\texttt{s}}(G)$ are the connected search number and the search number of $G$, respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using $k$ searchers into a (monotone) connected one using $2k+3$ searchers and starting at an arbitrary homebase.