论文标题
多项式内核，用于广义统治问题
Polynomial Kernels for Generalized Domination Problems
论文作者
论文摘要
在本文中，我们研究了称为[$σ，ρ$]主导设置问题的广义支配问题的参数化复杂性。这个问题概括了许多问题，包括最低占主导地位的问题及其许多变体。对[$σ，ρ$]的参数化复杂性主导着由树宽参数化的集合问题。在这里，确定了使问题处理的集合$σ$和$ρ$的属性[1]。我们考虑较大的参数并研究多项式大小的内核的存在。当$σ$和$ρ$有限时，我们确定[$σ，ρ$]主导设置问题参数为coartion coper的确切条件。我们的下限和上限结果也可以扩展到更一般的条件，也可以扩展到更小的参数。
In this paper, we study the parameterized complexity of a generalized domination problem called the [$σ, ρ$] Dominating Set problem. This problem generalizes a large number of problems including the Minimum Dominating Set problem and its many variants. The parameterized complexity of the [$σ, ρ$] Dominating Set problem parameterized by treewidth is well studied. Here the properties of the sets $σ$ and $ρ$ that make the problem tractable are identified [1]. We consider a larger parameter and investigate the existence of polynomial sized kernels. When $σ$ and $ρ$ are finite, we identify the exact condition when the [$σ, ρ$] Dominating Set problem parameterized by vertex cover admits polynomial kernels. Our lower and upper bound results can also be extended to more general conditions and provably smaller parameters as well.
