Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

(Meta) Kernelization

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.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904532
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Thursday, November 14, 2013 - 4:13:13 PM
Last modification on : Friday, November 20, 2020 - 4:22:03 PM

Links full text

Identifiers

  • HAL Id : lirmm-00904532, version 1
  • ARXIV : 0904.0727

Collections

Citation

Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, et al.. (Meta) Kernelization. 2013. ⟨lirmm-00904532⟩

Share

Metrics

Record views

171