Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma

Abstract

Given a graph and two integers $k$ and $\ell$, Partial Vertex Cover asks for a set of at most $k$ vertices whose deletion results in a graph with at most $\ell$ edges. Based on the expansion lemma, we provide a problem kernel with $(\ell +2)(k+\ell )$ vertices. We then introduce a new, additive version of the expansion lemma and show it can be used to prove a kernel with $(\ell +1)(k+\ell )$ vertices for $\ell \ge 1$.