论文标题
用稀疏图覆盖许多（或很少）的边缘（或几个）边缘
Covering Many (or Few) Edges with k Vertices in Sparse Graphs
论文作者
论文摘要
我们研究以下两个固定的核能优化问题（最大化和最小化变体）。对于固定的$α$，在零和一个之间，我们得到了一个图形，两个数字$ k \ in \ mathbb {n} $和\ mathbb {q} $ in \ mathbb {n} $和$ t \。任务是找到一个至少具有价值的$ k $顶点的顶点子集$ s $（最多可用于最小化）$ t $。在这里，顶点集的值计算为$α$乘以$ s $ in $ s $加上一个端点的边数的数量，加上$ 1-α$乘以$ s $的边缘数量的边缘数量。这两个问题概括了许多突出的图形问题，例如浓密的$ k $ -subgraph，最稀少的$ k $ -subgraph，部分顶点封面和Max（$ k $，$ n-k $） - 剪切。 在这项工作中，我们在几种由结构参数描述的几种类型的稀疏图上完成了它们的参数化复杂性图。特别是，我们为这些问题提供了内核化算法和内核下限。我们的内核的一个令人惊讶的后果是，部分顶点覆盖物和最大$（k，n-k）$不仅以相同的方式剪切，而且可以通过同一算法获得两个问题的内核。
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed $α$ between zero and one we are given a graph and two numbers $k \in \mathbb{N}$ and $t \in \mathbb{Q}$. The task is to find a vertex subset $S$ of exactly $k$ vertices that has value at least (resp. at most for minimization) $t$. Here, the value of a vertex set computes as $α$ times the number of edges with exactly one endpoint in $S$ plus $1-α$ times the number of edges with both endpoints in $S$. These two problems generalize many prominent graph problems, such as Densest $k$-Subgraph, Sparsest $k$-Subgraph, Partial Vertex Cover, and Max ($k$,$n-k$)-Cut. In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max $(k,n-k)$-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.
