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 NP⁄⊆coNP/poly, we prove that for any minor-closed graph class G, Feedback Vertex Set parameterized by the size of a modulator to G has a polynomial kernel if and only if G has bounded elimination distance to a forest. This captures and generalizes all existing kernels for structural parameterizations of the Feedback Vertex Set problem. Download : Download high-res image (47KB)Download : Download full-size image

Abstract 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 $$\textrm{NP}\not \subseteq \textrm{coNP}/\textrm{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.