论文标题
路径集包装的参数化复杂性
Parameterized Complexity of Path Set Packing
论文作者
论文摘要
在路径集包装中，输入是一个无向图$ g $，$ g $中的简单路径的$ \ calp $和一个正整数$ k $。问题是要确定是否存在$ \ calp $中的$ K $ edge-diserchint路径。我们研究了相对于自然和结构参数的路径集填料的参数化复杂性。我们表明，问题是$ W [1] $ - 相对于顶点盖号码而言，$ W [1] $ - 难以尊重路径宽，加上最高度和解决方案尺寸。这些结果回答了Cocoon 2018中提出的一个空旷的问题。在正面，我们提出了通过反馈顶点数字加上最高度来参数的FPT算法，并提供了由TreeWidth参数化的FPT算法，加上最大程度加上最大长度以及$ \ CALP $中的路径的最大长度。这些阳性结果补充了相对于FPT算法中使用的任何参数的任何子集的路径集填料的硬度。我们还为最大路径设置包装问题提供了$ 4 $ - APPRXIMATION算法，该算法在通过反馈边缘数字参数化时以FPT时间运行。
In Path Set Packing, the input is an undirected graph $G$, a collection $\calp$ of simple paths in $G$, and a positive integer $k$. The problem is to decide whether there exist $k$ edge-disjoint paths in $\calp$. 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 number, 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 present an FPT algorithm parameterized by feedback vertex number plus maximum degree, and present an FPT algorithm parameterized by treewidth plus maximum degree plus maximum length of a path in $\calp$. These positive results complement the hardness of Path Set Packing with respect to any subset of the parameters used in the FPT algorithms. We also give a $4$-approximation algorithm for maximum path set packing problem which runs in FPT time when parameterized by feedback edge number.
