Minimum length path decompositions
| Autor: | Dereniowski, Dariusz, Kubiak, Wieslaw, Zwols, Yori |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Journal of Computer and System Sciences 81 (2015) 1715-1747 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.jcss.2015.06.011 |
| Popis: | 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\geq 4$, and is also NP-complete for any fixed $l\geq 2$. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph $G$ and integers $k\leq 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\geq 5$ and it is polynomial-time for any $k\leq 3$. This leaves open the case $k=4$ for connected graphs. Comment: Work presented at the 5th Workshop on GRAph Searching, Theory and Applications (GRASTA 2012), Banff International Research Station, Banff, AB, Canada |
| Databáze: | arXiv |
| Externí odkaz: |
|