论文标题
顶点盖和反馈顶点在结构保证上方和下方设置
Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees
论文作者
论文摘要
通过解决方案尺寸K参数为参数的顶点覆盖物是典型的固定参数可拖动问题。当参数很小时，FPT算法最有趣。 K上的几个下限是众所周知的，例如匹配的最大尺寸。这导致了关于溶液尺寸K和下限的差异的角度研究的一系列研究。对于问题为fpt的这种下限的最突出的情况是匹配数或最佳分数LP解决方案。我们通过K和其他图参数之间的差异来研究参数化，包括反馈顶点号，退化性，群集删除数和树宽，目的是找到上述差异参数化的固定参数障碍性的边界。我们还考虑了反馈顶点集问题的类似参数化。
Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several lower bounds on k are well-known, such as the maximum size of a matching. This has led to a line of research on parameterizations of Vertex Cover by the difference of the solution size k and a lower bound. The most prominent cases for such lower bounds for which the problem is FPT are the matching number or the optimal fractional LP solution. We investigate parameterizations by the difference between k and other graph parameters including the feedback vertex number, the degeneracy, cluster deletion number, and treewidth with the goal of finding the border of fixed-parameter tractability for said difference parameterizations. We also consider similar parameterizations of the Feedback Vertex Set problem.
