(Meta) Kernelization

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

Research output: Contribution to journalArticleAcademicpeer-review

45 Citations (Scopus)
35 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 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
Article number44
Number of pages69
JournalJournal of the ACM
Volume63
Issue number5
DOIs
Publication statusPublished - 1 Nov 2016

Keywords

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

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

Cite this