Parameterized Complexity of (A,ℓ)-Path Packing

08/08/2020
by   Rémy Belmonte, et al.
0

Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)-Path Packing problem asks to find k vertex-disjoint paths of length ℓ that have endpoints in A and internal points in V ∖ A. We study the parameterized complexity of this problem with parameters |A|, ℓ, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ≤ 3, while it is NP-complete for constant ℓ≥ 4. We also show that the problem is W[1]-hard parameterized by pathwidth+|A|, while it is fixed-parameter tractable parameterized by treewidth+ℓ.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset