论文标题
反馈顶点的内核通过取消森林的距离设置
Kernelization for Feedback Vertex Set via Elimination Distance to a Forest
论文作者
论文摘要
我们研究了无向反馈顶点集问题的有效预处理，这是图理论中的一个基本问题，该问题要求一个最小尺寸的顶点集，其去除可产生一个无环图。更确切地说，我们旨在确定该问题的哪个参数化允许多项式内核。尽管基于最近引入的桥梁深度概念的相关顶点覆盖问题的特征是众所周知的，但是否可以将其推广到反馈顶点集合仍然是一个开放的问题。答案被证明是负面的。用于反馈顶点集的结构参数化的多项式内核的存在受到森林的消除距离。根据标准假设是NP不是conp/poly的子集，我们证明，对于任何次要闭合的Graph类$ \ MATHCAL G $，反馈顶点集由调制器的大小到$ \ Mathcal G $进行参数化，并且仅在$ \ Mathcal g $的情况下，只有在y Mathcal g $的情况下，只有在y Mathcal g $上都有多项式内核。这捕获并概括了所有现有内核，以进行反馈顶点集问题的结构参数化。
We study efficient preprocessing for the undirected Feedback Vertex Set problem, a fundamental problem in graph theory which asks for a minimum-sized vertex set whose removal yields an acyclic graph. More precisely, we aim to determine for which parameterizations this problem admits a polynomial kernel. While a characterization is known for the related Vertex Cover problem based on the recently introduced notion of bridge-depth, it remained an open problem whether this could be generalized to Feedback Vertex Set. The answer turns out to be negative; the existence of polynomial kernels for structural parameterizations for Feedback Vertex Set is governed by the elimination distance to a forest. Under the standard assumption that NP is not a subset of coNP/poly, we prove that for any minor-closed graph class $\mathcal G$, Feedback Vertex Set parameterized by the size of a modulator to $\mathcal G$ has a polynomial kernel if and only if $\mathcal G$ has bounded elimination distance to a forest. This captures and generalizes all existing kernels for structural parameterizations of the Feedback Vertex Set problem.
