(Meta) Kernelization

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.

Authors

• Hans L. Bodlaender
• Fedor V. Fomin
• Daniel Lokshtanov
• Eelko Penninkx
• Saket Saurabh 0001
• Dimitrios M. Thilikos

Keywords

• Kernel
• Polynomials
• Computer science
• Informatics
• Mathematics
• Logic
• History
• Mathematical analysis
• NP-hard problem
• Councils
• Positive Integer
• Specific Rules
• Linear Kernel
• Problem Parameters
• Polynomial Kernel
• Planar Graphs
• Dominating Set
• Finite Index
• Graph Problems
• Order Logic
• Compactness Properties
• State Machine
• Radial Distance
• Complex Parameters
• Problem Instances
• Polynomial-time Algorithm
• Joining Tree
• Normal Distance
• Spanning Tree
• Problem In Question
• Questions For Further Research
• Class Of Graphs
• Multigraph
• Proof Of Case
• Kernelization
• Polynonial Time Preprocessing
• Parameterized Algorithms
• Counting Monadic Second Order Logic
• Finite State
• Finite Integer Index
• Graphs of Bounded Genus