(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 kernelzation. 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 version of the paper of FOCS 2009

References in corpus (1)

• Diameter and Treewidth in Minor-Closed Graph Families

Cited by in corpus (9)

• Hierarchies of Inefficient Kernelizability
• Designing FPT algorithms for cut problems using randomized contractions
• Contracting Graphs to Paths and Trees
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• Linear kernels for k-tuple and liar's domination in bounded genus graphs
• Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
• A Polynomial kernel for Proper Interval Vertex Deletion
• What makes normalized weighted satisfiability tractable
• Confronting Intractability via Parameters