(Meta) kernelization

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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-Pósa property we obtain various new results on linear kernels for a number of packing and covering problems.

Original languageEnglish (US)
Title of host publicationProceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Number of pages10
StatePublished - 2009
Event50th Annual Symposium on Foundations of Computer Science, FOCS 2009 - Atlanta, GA, United States
Duration: Oct 25 2009Oct 27 2009

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Other50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Country/TerritoryUnited States
CityAtlanta, GA

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of '(Meta) kernelization'. Together they form a unique fingerprint.

Cite this