Finding small-width connected path decompositions in polynomial time

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$isconnectedforeach$i\in{1,\ldots,l}$\mathrm{.}Theconnectedpathwidthof$G$isthentheminimumwidthoverallconnectedpathdecompositionsof$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.