Skip to Main content Skip to Navigation
Journal articles

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

Cited literature [73 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Monday, January 22, 2018 - 8:40:43 AM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Thursday, May 24, 2018 - 7:06:03 AM


Files produced by the author(s)




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⟩



Record views


Files downloads