Hols, EvaMaria C. ;
Kratsch, Stefan
Smaller Parameters for Vertex Cover Kernelization
Abstract
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a kernel with O(X^{12}) vertices when X is a vertex set such that each connected component of GX contains at most one cycle, i.e., X is a modulator to a pseudoforest. We strongly generalize this result by using modulators to dquasiforests, i.e., graphs where each connected component has a feedback vertex set of size at most d, and obtain kernels with O(X^{3d+9}) vertices. Our result relies on proving that minimal blocking sets in a dquasiforest have size at most d+2. This bound is tight and there is a related lower bound of O(X^{d+2epsilon}) on the bit size of kernels.
In fact, we also get bounds for minimal blocking sets of more general graph classes: For dquasibipartite graphs, where each connected component can be made bipartite by deleting at most d vertices, we get the same tight bound of d+2 vertices. For graphs whose connected components each have a vertex cover of cost at most d more than the best fractional vertex cover, which we call dquasiintegral, we show that minimal blocking sets have size at most 2d+2, which is also tight. Combined with existing randomized polynomial kernelizations this leads to randomized polynomial kernelizations for modulators to dquasibipartite and dquasiintegral graphs. There are lower bounds of O(X^{d+2epsilon}) and O(X^{2d+2epsilon}) for the bit size of such kernels.
BibTeX  Entry
@InProceedings{hols_et_al:LIPIcs:2018:8563,
author = {EvaMaria C. Hols and Stefan Kratsch},
title = {{Smaller Parameters for Vertex Cover Kernelization}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {20:120:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8563},
URN = {urn:nbn:de:0030drops85638},
doi = {10.4230/LIPIcs.IPEC.2017.20},
annote = {Keywords: Vertex Cover, Kernelization, Structural Parameterization}
}
02.03.2018
Keywords: 

Vertex Cover, Kernelization, Structural Parameterization 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

02.03.2018 