1. The complexity of minimum-length path decompositions.
- Author
-
Dereniowski, Dariusz, Kubiak, Wieslaw, and Zwols, Yori
- Subjects
- *
COMPUTATIONAL complexity , *PATHS & cycles in graph theory , *MATHEMATICAL decomposition , *GENERALIZATION , *GRAPH theory - Abstract
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 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 ≥ 4 , and also for any fixed l ≥ 2 . On the other hand, we give a polynomial-time 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 . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF