(Meta) Kernelization

H.L. Bodlaender, F.V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, D.M. Thilikos

Research output: Contribution to journalArticleAcademic

18 Downloads (Pure)

Abstract

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 kernelzation. 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
JournalarXiv
Publication statusPublished - 4 Apr 2009
Externally publishedYes

Bibliographical note

Complete version of the paper of FOCS 2009

Keywords

  • cs.DM
  • cs.DS
  • 05C85, 68W05, 68R10,
  • F.2.2; G.2.2

Fingerprint

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

Cite this