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

c P

of

G

such that the width of

c P

is at most

k

and the number of bags in

c P

, i.e., the emph{length} of

c P

, 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 g e q 4

, and is also NP-complete for any fixed

l g e q 2

. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph

G

and integers

k l e q 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 g e q 5

and it is polynomial-time for any

k l e q 3

. This leaves open the case

k = 4

for connected graphs.

Recommendations

Cites Work

Cited In (9)

This page was built for publication: The complexity of minimum-length path decompositions