Minimum length path decompositions

Dariusz Dereniowski, Wieslaw Kubiak, Yori Zwols

We consider a bi-criteria generalization of the pathwidth problem, where, for given integers $k,l$ and a graph $G$, we ask whether there exists a path decomposition $\cP$ of $G$ su…