(Meta) Kernelization

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

Research output: Contribution to journalArticlepeer-review


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, one can reduce the size of the instance I to a polynomial in k while preserving the answer. In this work, we give two meta-Theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability 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 coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.

Original languageEnglish (US)
Article number44
JournalJournal of the ACM
Issue number5
StatePublished - Nov 2016


  • embedded graphs
  • finite integer index
  • kernelization
  • Monadic second-order logic
  • parameterized complexity
  • preprocessing
  • protrusions
  • treewidth

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


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

Cite this