(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 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.
Type de document :
Article dans une revue
Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (5), pp.#44. 〈10.1145/2973749〉
Liste complète des métadonnées

Littérature citée [89 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483628
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 22 janvier 2018 - 08:40:43
Dernière modification le : lundi 22 janvier 2018 - 10:12:13

Fichier

0904.0727.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, et al.. (Meta) Kernelization. Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (5), pp.#44. 〈10.1145/2973749〉. 〈lirmm-01483628〉

Partager

Métriques

Consultations de la notice

44