Minimum length path decompositions
| Title: | Minimum length path decompositions |
|---|---|
| Authors: | Dereniowski, Dariusz, Kubiak, Wieslaw, Zwols, Yori |
| Source: | Journal of Computer and System Sciences 81 (2015) 1715-1747 |
| Publication Year: | 2013 |
| Collection: | Computer Science Mathematics |
| Subject Terms: | Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, 68Q25, 05C85, 68R10 |
| More Details: | 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 |
| Document Type: | Working Paper |
| DOI: | 10.1016/j.jcss.2015.06.011 |
| Access URL: | http://arxiv.org/abs/1302.2788 |
| Accession Number: | edsarx.1302.2788 |
| Database: | arXiv |
| DOI: | 10.1016/j.jcss.2015.06.011 |
|---|