Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
复制标题
DOI：
10.4230/lipics.stacs.2020.36
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Eva-Maria C. Hols;Stefan Kratsch;A. Pieterse
中科院分区：
文献类型：
--
作者：
Eva-Maria C. Hols;Stefan Kratsch;A. Pieterse
顶点覆盖问题是研究参数化复杂度多项式核化问题，即研究np困难问题的可证明和有效预处理的关键问题。由于对不同参数和图类的顶点覆盖的核化有各种各样的正面和负面结果，我们试图使用所谓的块集来统一和推广它们，块集在许多结果中起着隐式和显式的作用。我们表明，在研究最多的设置中，通过指定图类$\mathcal{C}$的删除集的大小参数化，有界最小块集大小是必要的，但不足以获得多项式核化。在温和的技术假设下，有界最小块集大小显示允许本质上紧密有效地减少连接组件的数量。然后，我们确定最小块集的确切最大大小，对于任何遗传类$\mathcal{C}$具有有界消除距离的图，包括有界树深度的图。对于某些非遗传类$\mathcal{C}$，我们得到了类似但不紧的界，包括类$\mathcal{C}_{LP}$，其中积分和分数顶点覆盖大小重合。这些边界允许我们导出顶点覆盖的多项式核，该多项式核由有界消除距离的图的删除集的大小参数化，例如，森林，二部或$\mathcal{C}_{LP}$图。
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets, which have played implicit and explicit roles in many results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class $\mathcal{C}$, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class $\mathcal{C}$, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes $\mathcal{C}$, including the class $\mathcal{C}_{LP}$ of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or $\mathcal{C}_{LP}$ graphs.