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.

翻译：我们调查了图形中顶点子子设置问题的预处理。 源自参数化复杂理论的内核化概念, 是一种正规化的有效预处理预处理概念, 目的是减少总体试量大小, 我们的重点是找到属于最佳解决方案的非空顶点设置。 这缩小了仍然需要找到的解决方案剩余部分的大小, 从而缩小了基于解决方案大小的参数化参数化的固定参数可移动算法的搜索空间。 我们引入了 C- 关键顶点概念, 这一概念包含在所有c- 近似解决方案中。 对于一些典型的组合问题, 如 Odccrocycour Transversal 和直接反馈 Vertex Set, 我们显示, 在温和的条件下, 多时预处理算法可以找到包含所有2个基本顶点的解决方案的组合, 利用包装/ 覆盖双重性 。 这导致 FPT 算法解决了这些问题, 因为在运行过程中的指数术语仅取决于解决方案中非必要脊柱点的数量。