Computer Science – Discrete Mathematics
Scientific paper
2009-04-04
Computer Science
Discrete Mathematics
Scientific paper
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.
Bodlaender Hans L.
Fomin Fedor V.
Lokshtanov Daniel
Penninkx Eelko
Saurabh Saket
No associations
LandOfFree
(Meta) Kernelization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with (Meta) Kernelization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (Meta) Kernelization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-123322