Parameterized Complexity of (A,ℓ)-Path Packing.

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 exactly ℓ 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 + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most ℓ . We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or ℓ is a constant. [ABSTRACT FROM AUTHOR]