Meta) Kernelization

摘要: Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics tackle computationally hard problems. In a parameterized problem, every I comes with positive integer k. The problem said admit polynomial kernel if, in time, we can k, while preserving answer. this paper, show that all problems expressible Counting Monadic Second Order Logic and satisfying compactness property on graphs bounded genus. Our second result have finite index satisfy weaker condition linear study kernels planar was initiated by seminal paper Alber, Fellows, Niedermeier [J. ACM, 2004 ] who showed Planar Dominating Set admits kernel. Following result, multitude been shown combining ideas Alber et al. specific reduction rules. theorems unify extend previously known kernelization results for graph Combining our Erdos-Posa obtain various new number packing covering