Polynomial Kernels for MSO-expressible Graph Problems

Robert Ganian (joint work with Friedrich Slivovsky and Stefan Szeider)

Kernelization is an algorithmic technique that has become the subject of a very active field in parameterized complexity. Kernelization can be considered as preprocessing with a performance guarantee that reduces an instance of a parameterized problem in polynomial time to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. It Is known that every decidable fi xed-parameter tractable problem admits a kernel, but the size of the kernel can have an exponential or even non-elementary dependence on the parameter. Thus research on kernelization is typically concerned with the question of whether a fi xed-parameter tractable problem admits a small, and in particular a polynomial, kernel.

Recently, theoretical tools have been developed to provide strong theoretical evidence that certain fi xed-parameter tractable problems parameterized by well-known parameters such as tree-width do not admit polynomial kernels. Thus structural parameters have been suggested that are somewhat weaker than tree-width, in order to admit polynomial kernels, such as the vertex cover number, max-leaf number, and neighborhood diversity.

We extend this line of research by introducing a new structural parameter that we call the rank-width cover number. We show that this parameter is more general than the standard structural parameters used for kernelization, and prove that it is possible to compute the rank-width cover number (along with the rank-width cover) of a graph in polynomial time. This is then used to obtain our main result - that every MSO model checking problem, parameterized by the rank-width cover number of the input graph, has a polynomial kernel. We also prove that this result can be extended from MSO model checking to LinEMSO optimization problems.