(Meta) Kernelization - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of the ACM (JACM) Year : 2016

(Meta) Kernelization


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.
Fichier principal
Vignette du fichier
0904.0727.pdf (1003.1 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01483628 , version 1 (22-01-2018)



Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, et al.. (Meta) Kernelization. Journal of the ACM (JACM), 2016, 63 (5), pp.#44. ⟨10.1145/2973749⟩. ⟨lirmm-01483628⟩
158 View
230 Download



Gmail Facebook X LinkedIn More