In this paper, we study the parameterized complexity of a generalized domination problem called the [${\sigma}, {\rho}$] 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 [${\sigma}, {\rho}$] Dominating Set problem parameterized by treewidth is well studied. Here the properties of the sets ${\sigma}$ and ${\rho}$ that make the problem tractable are identified [1]. We consider a larger parameter and investigate the existence of polynomial sized kernels. When ${\sigma}$ and ${\rho}$ are finite, we identify the exact condition when the [${\sigma}, {\rho}$] 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.
翻译:在本文中, 我们研究一个叫做 [ $sigma}, $rho] 的普遍统治问题的参数复杂性。 这个问题概括了许多问题, 包括最小主导区问题及其多种变体。 [ $sigma] 、 $rho] 的参数复杂性, 以树枝为参数的集成问题参数性能得到了很好研究。 使问题能够被拖动的集成问题特性在这里被确定 [1] 。 我们考虑一个更大的参数, 并调查多球大小的内核的存在。 当$sigma] 和 $ rho] 问题是有限的时, 我们确定由顶层覆盖参数参数参数的集成问题的确切条件 。 我们的下限和上限结果也可以扩大到更一般的条件和小的参数 。