论文标题
部分顶点覆盖（添加剂）膨胀引理的内核化
Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma
论文作者
论文摘要
给定图形和两个整数$ k $和$ \ ell $，部分顶点盖子要求一组最多$ k $的顶点，其删除的删除最多最多$ \ ell $ edges。基于扩展引理，我们提供了一个问题内核，其中$（\ ell + 2）（k + \ ell）$ Vertices。然后，我们引入了扩展引理的新添加版，并显示它可用于证明$（\ ell + 1）（k + \ ell）$ dertices $ \ ell \ ell \ ge 1 $。
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$.
