The complexity of minimum-length path decompositions

• We consider graphs of pathwidth k and focus on minimum-length path decompositions.
• We give a polynomial-time algorithm for k≤3k≤3.
• The problem is NP-hard for k≥4k≥4.
• The problem is NP-hard even for connected graphs for k≥5k≥5.
• The complexity for connected graphs with k=4k=4 remains open.

We consider a bicriterion generalization of the pathwidth problem: given integers k,lk,l and a graph G, does there exist a path decomposition of G of width at most k and length (i.e., number of bags) 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  , the generalized problem is NP-complete for any fixed k≥4k≥4, and also for any fixed l≥2l≥2. On the other hand, we give a polynomial-time algorithm that constructs a minimum-length path decomposition of width at most k≤3k≤3 for any disconnected input graph. As a by-product, we obtain an almost complete classification for connected graphs: the problem is NP-complete for any fixed k≥5k≥5, and polynomial for any k≤3k≤3.