A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
Stefan Kratsch · SIAM Journal on Discrete Mathematics · 2018
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 $\mathcal{O}^*(2^k)$, making it fixed-parameter tractable (FPT) with respect to $k$. While the fastest known algorithm takes only time $\mathcal{O}^*(1.2738^k)$, 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 $\mathcal{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. ACM Trans. Algorithms, 11 (2014), pp. 15:1--15:31]. Since $p\leq 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 $\ell=k-(2LP(G)-MM(G))$. They give an algorithm of running time $\mathcal{O}^*(3^\ell)$, proving that vertex cover is FPT in $\ell$. It can be easily observed that $\ell\leq p$ whereas $p$ cannot be bounded in terms of $\ell$ alone. We complement the work of Garg and Philip by proving that vertex cover admits a randomized polynomial kernelization in terms of $\ell$, i.e., an efficient preprocessing to size polynomial in $\ell$. 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].