Bougeret, Marin ;
Jansen, Bart M. P. ;
Sau, Ignasi
BridgeDepth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
Abstract
We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomialtime 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 ℱ, such as forests, graphs of bounded treedepth, and graphs of maximum degree two. We set out to find the most general graph classes ℱ for which Vertex Cover parameterized by the vertexdeletion distance of the input graph to ℱ, admits a polynomial kernelization. We give a complete characterization of the minorclosed graph families ℱ for which such a kernelization exists. We introduce a new graph parameter called bridgedepth, and prove that a polynomial kernelization exists if and only if ℱ has bounded bridgedepth. The proof is based on an interesting connection between bridgedepth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.
BibTeX  Entry
@InProceedings{bougeret_et_al:LIPIcs:2020:12423,
author = {Marin Bougeret and Bart M. P. Jansen and Ignasi Sau},
title = {{BridgeDepth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {16:116:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12423},
URN = {urn:nbn:de:0030drops124238},
doi = {10.4230/LIPIcs.ICALP.2020.16},
annote = {Keywords: vertex cover, parameterized complexity, polynomial kernel, structural parameterization, bridgedepth}
}
29.06.2020
Keywords: 

vertex cover, parameterized complexity, polynomial kernel, structural parameterization, bridgedepth 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 