(Meta) Kernelization

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

58 Citaten (Scopus)
62 Downloads (Pure)


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.

Originele taal-2Engels
Aantal pagina's69
TijdschriftJournal of the ACM
Nummer van het tijdschrift5
StatusGepubliceerd - 1 nov. 2016


Duik in de onderzoeksthema's van '(Meta) Kernelization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit