Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma

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