Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma

11/13/2022

∙

by   Tomohiro Koana, et al.

∙

0

∙

share

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