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

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
Titel47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
RedacteurenArtur Czumaj, Anuj Dawar, Emanuela Merelli
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN van elektronische versie9783959771382
DOI's
StatusGepubliceerd - 1 jun 2020
Evenement47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 - Virtual, Online, Duitsland
Duur: 8 jul 202011 jul 2020

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume168
ISSN van geprinte versie1868-8969

Congres

Congres47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
LandDuitsland
StadVirtual, Online
Periode8/07/2011/07/20

Vingerafdruk Duik in de onderzoeksthema's van 'Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel'. Samen vormen ze een unieke vingerafdruk.

Citeer dit