(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 metadatas

Cited literature [73 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483628
Contributor : Dimitrios M. Thilikos <>
Submitted on : Monday, January 22, 2018 - 8:40:43 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Thursday, May 24, 2018 - 7:06:03 AM

File

0904.0727.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

209

Files downloads

123