Skip to Main content Skip to Navigation
Conference papers

Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

Marin Bougeret 1 Bart Jansen 2 Ignasi Sau Valls 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance (G, k) of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a predetermined complexity parameter of G. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce G to a member of a simple graph class F, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes F for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to F, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families F for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if F has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.
Document type :
Conference papers
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Isabelle Gouat <>
Submitted on : Thursday, November 5, 2020 - 9:40:46 PM
Last modification on : Monday, December 14, 2020 - 5:27:16 PM
Long-term archiving on: : Saturday, February 6, 2021 - 8:19:01 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Marin Bougeret, Bart Jansen, Ignasi Sau Valls. Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel. 47th International Colloquium on Automata, Languages, and Programming (ICALP), Jul 2020, Saarbrücken, Germany. pp.16:1--16:19, ⟨10.4230/LIPIcs.ICALP.2020.16⟩. ⟨lirmm-02991230⟩



Record views


Files downloads