A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter

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⊆ 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ᵏ), making it fixed-parameter tractable (FPT) with respect to k. While the fastest known algorithm takes only time O^*(1.2738ᵏ), much stronger improvements have been obtained by studying parameters that are smaller than k. Apart from treewidth-related results, the arguably best algorithm for vertex cover runs in time O^*(2.3146ᵖ), where $p=k-LP(G)$ is only the excess of the solution size k over the best fractional vertex cover [Lokshtanov et al. ACM Trans. Algorithms, 11 (2014), pp. 15:1--15:31]. 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, Proceedings of the Symposium on Discrete Algorithms, 2016, pp. 1152--1166] 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 =k-(2LP(G)-MM(G)). They give an algorithm of running time O^*(3⁾, proving that vertex cover is FPT in . It can be easily observed that ≤ p whereas p cannot be bounded in terms of alone. We complement the work of Garg and Philip by proving that vertex cover admits a randomized polynomial kernelization in terms of , i.e., an efficient preprocessing to size polynomial in . This improves over parameter $p=k-LP(G)$ for which this was previously known [Kratsch and Wahlström, Proceedings of the IEEE Symposium on Foundations of Computer Science, 2012, pp. 450--459].