Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel

Marin Bougeret, Bart M.P. Jansen, Ignasi Sau

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 pre-determined 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.

Original languageEnglish
Title of host publication47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
EditorsArtur Czumaj, Anuj Dawar, Emanuela Merelli
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771382
DOIs
Publication statusPublished - 1 Jun 2020
Event47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 - Virtual, Online, Germany
Duration: 8 Jul 202011 Jul 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume168
ISSN (Print)1868-8969

Conference

Conference47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
CountryGermany
CityVirtual, Online
Period8/07/2011/07/20

Keywords

  • Bridge-depth
  • Parameterized complexity
  • Polynomial kernel
  • Structural parameterization
  • Vertex cover

Fingerprint Dive into the research topics of 'Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel'. Together they form a unique fingerprint.

Cite this