Meta-kernelization with Structural Parameters

Abstract Meta-kernelization theorems are general results that provide polynomial kernels for large classes of parameterized problems. The known meta-kernelization theorems, in particular the results of Bodlaender et al. (FOCS’09) and of Fomin et al. (FOCS’10), apply to optimization problems parameterized by solution size. We present meta-kernelization theorems that use structural parameters of the input and not the solution size. Let \(\mathcal{C}\) be a graph class. We define the \(\mathcal{C}\) - cover number of a graph to be the smallest number of modules the vertex set can be partitioned into such that each module induces a subgraph that belongs to the class \(\mathcal{C}\). We show that each graph problem that can be expressed in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the \(\mathcal{C}\) - cover number for any fixed class \(\mathcal{C}\) of bounded rank-width (or equivalently, of bounded clique-width, or bounded Boolean-width). Many graph problems such as c -Coloring, c -Domatic Number and c -Clique Cover are covered by this meta-kernelization result. Our second result applies to MSO expressible optimization problems, such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique. We show that these problems admit a polynomial annotated kernel with a linear number of vertices.

Authors

• Robert Ganian
• Friedrich Slivovsky
• Stefan Szeider

Keywords

No keywords are indexed for this paper.