论文标题
$（a，\ ell）$ - 路径包装的参数化复杂度
Parameterized Complexity of $(A,\ell)$-Path Packing
论文作者
论文摘要
给定图形$ g =（v，e）$，$ a \ subseteq v $，以及整数$ k $和$ \ ell $，\ textsc {$（a，\ ell）$ - 路径包装}问题要求查找$ k $ vertex-disjoint路径的长度$ \ ell $ \ ell $ en of a $ n $ a $ a $ a $ v \ v \ v \ v \ v \ v \ a $ n en en en en en en en en en en en en en en en en n en en n of。我们研究了此问题与参数的参数化复杂性$ | a | $，$ \ ell $，$ k $，weetWidth，pathWidth及其组合。我们提出与这些参数相对于这些参数形成鲜明对比的。除其他结果外，我们还表明，当$ \ ell \ le 3 $时，问题是多项式时间溶液，而对于常量$ \ ell \ ge 4 $，它是NP的np填充。我们还表明，问题是W [1] -HARD由路径宽$ {}+| a | $参数化，而固定参数可通过TreeWidth $ {}}+\ ell $进行固定参数处理。
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$.
