  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 the first meta-kernelization
theorems that use a structural parameters of the input and not the solution
size. Let C be a graph class. We define the C-cover number of a graph to be a
the smallest number of modules the vertex set can be partitioned into, such
that each module induces a subgraph that belongs to the class 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 C-cover number for any fixed class C of bounded rank-width (or
equivalently, of bounded clique-width, or bounded Boolean width). Many graph
problems such as Independent Dominating Set, c-Coloring, and c-Domatic Number
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.
