The complexity of minimum-length path decompositions

We consider a bicriterion generalization of the pathwidth problem: given integers k, 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 Il 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 >= 4, and also for any fixed l >= 2. On the other hand, we give a polynomialtime algorithm that constructs a minimum-length path decomposition of width at most k <= 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 >= 5, and polynomial for any k <= 3. (C) 2015 Elsevier Inc. All rights reserved.