Abstract
In the Vertex Cover problem we are given a graph G=(V,E) and an integer k and have to determine whether there is a set X subseteq V of size at most k such that each edge in E has at least one endpoint in X. The problem can be easily solved in time O^*(2^k), making it fixedparameter tractable (FPT) with respect to k. While the fastest known algorithm takes only time O^*(1.2738^k), much stronger improvements have been obtained by studying parameters that are smaller than k. Apart from treewidthrelated results, the arguably best algorithm for Vertex Cover runs in time O^*(2.3146^p), where p = k  LP(G) is only the excess of the solution size k over the best fractional vertex cover [Lokshtanov et al., TALG 2014]. Since p <= k but k cannot be bounded in terms of p alone, this strictly increases the range of tractable instances.
Recently, Garg and Philip (SODA 2016) greatly contributed to understanding the parameterized complexity of the Vertex Cover problem. They prove that 2LP(G)  MM(G) is a lower bound for the vertex cover size of G, where MM(G) is the size of a largest matching of G, and proceed to study parameter l = k  (2LP(G)MM(G)). They give an algorithm of running time O^*(3^l), proving that Vertex Cover is FPT in l. It can be easily observed that l <= p whereas p cannot be bounded in terms of l alone. We complement the work of Garg and Philip by proving that Vertex Cover admits a randomized polynomial kernelization in terms of l, i.e., an efficient preprocessing to size polynomial in l. This improves over parameter p = k  LP(G) for which this was previously known [Kratsch and WahlstrÃ¶m, FOCS 2012].
BibTeX  Entry
@InProceedings{kratsch:LIPIcs:2016:6406,
author = {Stefan Kratsch},
title = {{A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {59:159:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6406},
URN = {urn:nbn:de:0030drops64066},
doi = {10.4230/LIPIcs.ESA.2016.59},
annote = {Keywords: Vertex cover, parameterized complexity, kernelization}
}
Keywords: 

Vertex cover, parameterized complexity, kernelization 
Collection: 

24th Annual European Symposium on Algorithms (ESA 2016) 
Issue Date: 

2016 
Date of publication: 

18.08.2016 