Name
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 . We consider graphs of pathwidth k and focus on minimum-length path decompositions.We give a polynomial-time algorithm for k ¿ 3 .The problem is NP-hard for k ¿ 4 .The problem is NP-hard even for connected graphs for k ¿ 5 .The complexity for connected graphs with k = 4 remains open. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.jcss.2015.06.011 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
Graph searching,Path decomposition,Pathwidth | Journal | 81 |
Issue | ISSN | Citations |
8 | Journal of Computer and System Sciences 81 (2015) 1715-1747 | 3 |
PageRank | References | Authors |
0.42 | 26 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dariusz Dereniowski | 1 | 178 | 26.76 |
| Wieslaw Kubiak | 2 | 540 | 62.61 |
| Yori Zwols | 3 | 45 | 6.34 |