Parameterized Complexity of $(A,\ell )$-Path Packing

Abstract

Given a graph $G=(V,E)$, $A\subseteq V$, and integers $k$ and $\ell$, the \textsc{$(A,\ell )$-Path Packing} problem asks to find $k$ vertex-disjoint paths of length $\ell$ that have endpoints in $A$ and internal points in $V\setminus A$. We study the parameterized complexity of this problem with parameters $|A|$, $\ell$, $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 $\ell \le 3$, while it is NP-complete for constant $\ell \ge 4$. We also show that the problem is W[1]-hard parameterized by pathwidth$+|A|$, while it is fixed-parameter tractable parameterized by treewidth$+\ell$.

22pages, IWOCA 2020