(Meta) Kernelization - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of the ACM (JACM) Année : 2016

(Meta) Kernelization

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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 Consultations
228 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More