The complexity of minimum-length path decompositions

Dariusz Dereniowski; Wieslaw Kubiak; Yori Zwols

doi:10.1016/j.jcss.2015.06.011

The complexity of minimum-length path decompositions

Abstract

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 P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classiﬁcation of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is ﬁxed-parameter tractable with respect to k, we prove that the generalized problem is NP-complete for any ﬁxed k >= 4, and is also NP-complete for any ﬁxed l >= 2. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph G and integers k <= 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 classiﬁcation of the problem in terms of k and l for connected graphs. Namely, the problem is NP-complete for any ﬁxed k >= 5 and it is polynomial-time for any k <= 3. This leaves open the case k = 4 for connected graphs.

Citations

4

CrossRef
0

Web of Science
5

Scopus

Authors (3)

Dariusz Dereniowski prof. dr hab. inż.
Wieslaw Kubiak
- Memorial University Faculty of Business Administration
Yori Zwols
- Google DeepMind -

Cite as

Full text

download paper

downloaded 16 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.jcss.2015.06.011
License: Copyright (2015 Elsevier Inc)

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: JOURNAL OF COMPUTER AND SYSTEM SCIENCES no. 81, edition 8, pages 1715 - 1747,
ISSN: 0022-0000
Language:: English
Publication year:: 2015
Bibliographic description:: Dereniowski D., Kubiak W., Zwols Y.: The complexity of minimum-length path decompositions// JOURNAL OF COMPUTER AND SYSTEM SCIENCES. -Vol. 81, iss. 8 (2015), s.1715-1747
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.jcss.2015.06.011
Verified by:: Gdańsk University of Technology