Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2020

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

Marin Bougeret
Ignasi Sau

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.
Fichier principal
Vignette du fichier
LIPIcs-ICALP-2020-16.pdf (1.23 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-02991230 , version 1 (05-11-2020)

Licence

Attribution

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More