Minimum length path decompositions

Abstract

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$ such that the width of $\cP$ is at most $k$ and the number of bags in $\cP$, i.e., the \emph{length} of $\cP$, is at most $l$. We provide a complete complexity classification of the problem in terms of $k$ and $l$ for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to $k$, we prove that the generalized problem is NP-complete for any fixed $k\ge 4$, and is also NP-complete for any fixed $l\ge 2$. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph $G$ and integers $k\le 3$ and $l>0$, constructs a path decomposition of width at most $k$ and length at most $l$, if any exists. As a by-product, we obtain an almost complete classification of the problem in terms of $k$ and $l$ for connected graphs. Namely, the problem is NP-complete for any fixed $k\ge 5$ and it is polynomial-time for any $k\le 3$. This leaves open the case $k=4$ for connected graphs.

Work presented at the 5th Workshop on GRAph Searching, Theory and Applications (GRASTA 2012), Banff International Research Station, Banff, AB, Canada

References in corpus (1)

• From Pathwidth to Connected Pathwidth

Cited by in corpus (2)

• Finding small-width connected path decompositions in polynomial time
• On tradeoffs between width- and fill-like graph parameters