2020/08/08 by Belmonte, Rémy, Hanaka, Tesshu, Kanzaki, Masaaki +6
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2008.03448
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+ℓ.