(Meta) Kernelization
(Meta) Kernelization
复制标题
DOI：
10.1145/2973749
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
H. Bodlaender;F. Fomin;D. Lokshtanov;Eelko Penninkx;Saket Saurabh;D. Thilikos
中科院分区：
文献类型：
--
作者：
H. Bodlaender;F. Fomin;D. Lokshtanov;Eelko Penninkx;Saket Saurabh;D. Thilikos
用于减少实例大小的多项式时间预处理是解决计算困难问题最常用的启发式方法之一。在参数化问题中，每个实例 I 都带有一个正整数 k。如果在多项式时间内，我们可以将实例 I 的大小减小到 k 中的多项式，同时保留答案，则该问题被称为承认多项式核。在本文中，我们证明了所有可以用计数一元二阶逻辑表达并满足紧性属性的问题都承认有界属图上的多项式核。我们的第二个结果是，所有具有有限整数索引并满足较弱紧性条件的问题都在有界亏格图上承认线性核。平面图上核的研究是由 Alber、Fellows 和 Niedermeier 的一篇开创性论文发起的 [J. ACM，2004] 证明了平面支配集承认线性核。根据这个结果，通过结合 Alber 等人的想法，许多问题都被证明在平面图上承认线性核。与问题特定的减少规则。我们的定理统一并扩展了所有先前已知的平面图问题的核化结果。将我们的定理与 Erdos-Posa 性质相结合，我们获得了针对许多包装和覆盖问题的线性核的各种新结果。
Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics to tackle computationally hard problems. In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, we can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this paper, we show that all problems expressible in Counting Monadic Second Order Logic and satisfying a compactness property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker compactness condition admit a linear kernel on graphs of bounded genus. The study of kernels on planar graphs was initiated by a seminal paper of Alber, Fellows, and Niedermeier [J. ACM, 2004 ] who showed that Planar Dominating Set admits a linear kernel. Following this result, a multitude of problems have been shown to admit linear kernels on planar graphs by combining the ideas of Alber et al. with problem specific reduction rules. Our theorems unify and extend all previously known kernelization results for planar graph problems. Combining our theorems with the Erdos-Posa property we obtain various new results on linear kernels for a number of packing and covering problems.