From Pathwidth to Connected Pathwidth

It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot \text{pw}(G)+1$, where $\text{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(d{k}^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 $\text{csn}(G)\le 2\text{sn}(G)+3$, where $\text{csn}(G)$ and $\text{sn}(G)$ are the connected search number and the search number of $G$. 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.