Finding small-width connected path decompositions in polynomial time

Dariusz Dereniowski, Dorota Osula, Paweł Rzążewski

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 ea…