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

Abstrakt

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.

Cytowania

4

CrossRef
0

Web of Science
5

Scopus

Autorzy (3)

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

Cytuj jako

Pełna treść

pobierz publikację

pobrano 13 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcss.2015.06.011
Licencja: Copyright (2015 Elsevier Inc)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: JOURNAL OF COMPUTER AND SYSTEM SCIENCES nr 81, wydanie 8, strony 1715 - 1747,
ISSN: 0022-0000
Język:: angielski
Rok wydania:: 2015
Opis bibliograficzny:: 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:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcss.2015.06.011
Weryfikacja:: Politechnika Gdańska