In PATH SET PACKING, the input is an undirected graph $G$, a collection $\cal P$ of simple paths in $G$, and a positive integer $k$. The problem is to decide whether there exist $k$ edge-disjoint paths in $\cal P$. We study the parameterized complexity of PATH SET PACKING with respect to both natural and structural parameters. We show that the problem is $W[1]$-hard with respect to vertex cover plus the maximum length of a path in $\cal P$, and $W[1]$-hard respect to pathwidth plus maximum degree plus solution size. These results answer an open question raised in COCOON 2018. On the positive side, we show an FPT algorithm parameterized by feedback vertex set plus maximum degree, and also show an FPT algorithm parameterized by treewidth plus maximum degree plus maximum length of a path in $\cal P$. Both the positive results complement the hardness of PATH SET PACKING with respect to any subset of the parameters used in the FPT algorithms.
翻译：在 PATH SET PACKING 中,输入是一个没有方向的图形 $G$, 一个以G$计算的简单路径的收藏 $\ cal P$, 一个正整数美元。 问题在于确定是否有美元P$的边缘- 分解路径。 我们研究了PATH SET PACKING在自然参数和结构参数方面的参数复杂性。 我们显示,在顶层覆盖加上一条路径的最大长度以$\ cal P$, 和 $W[ 1]$- 硬路径加最大程度加溶液大小。 这些结果回答了在COCOON 2018 中提出的一个开放式问题。 在积极的一面, 我们用反馈垂直设置加最大程度来显示 FPT 算法参数参数, 并以树with 加上最大程度加上一条路径以 $\ cal P$表示。 两种肯定的结果都补充了 PATH SET PACKINKE 与FPT 算法中使用的任何参数的硬性。
相关内容
微信扫码咨询专知VIP会员