论文标题
通过基本顶点降低搜索空间
Search-Space Reduction via Essential Vertices
论文作者
论文摘要
我们研究了图形上顶点 - 掩体问题的预处理。虽然源自参数化复杂性理论的内核化概念是旨在降低总实例大小的可证明有效预处理的形式化，但我们的重点是寻找属于最佳解决方案的非空角度集。这降低了仍然必须找到的解决方案的其余部分的大小，因此根据解决方案大小缩小了固定参数可拖动算法的搜索空间，以进行参数化。我们介绍了一个c符号顶点的概念，该概念均包含在所有c- approximate溶液中。对于几个经典的组合问题，例如奇数循环横向和有向反馈顶点集，我们表明在轻度条件下，多项式时间预处理算法可以通过利用包装/覆盖双重性来找到包含所有2个面向角色的最佳解决方案的子集。这导致FPT算法解决了这些问题，在这些问题中，在运行时间中的指数项仅取决于解决方案中的非代表顶点的数量。
We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, our focus is on finding a non-empty vertex set that belongs to an optimal solution. This decreases the size of the remaining part of the solution which still has to be found, and therefore shrinks the search space of fixed-parameter tractable algorithms for parameterizations based on the solution size. We introduce the notion of a c-essential vertex as one that is contained in all c-approximate solutions. For several classic combinatorial problems such as Odd Cycle Transversal and Directed Feedback Vertex Set, we show that under mild conditions a polynomial-time preprocessing algorithm can find a subset of an optimal solution that contains all 2-essential vertices, by exploiting packing/covering duality. This leads to FPT algorithms to solve these problems where the exponential term in the running time depends only on the number of non-essential vertices in the solution.
