Meta-kernelization with structural parameters


This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on


Year of publication 2016
Type Article in Periodical
Magazine / Source Journal of Computer and System Sciences
MU Faculty or unit

Faculty of Informatics

Keywords Boolean-width; Clique-width; Kernelization; Modular decomposition; Monadic second-order logic; Parameterized complexity; Rank-width
Description Kernelization is a polynomial-time algorithm that reduces an instance of a parameterized problem to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. In this paper we present meta-theorems that provide polynomial kernels for large classes of graph problems parameterized by a structural parameter of the input graph. Let be an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the -cover number of a graph to be the smallest number of modules its vertex set can be partitioned into, such that each module induces a subgraph that belongs to . We show that each decision problem on graphs which is expressible in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the -cover number. We provide similar results for MSO expressible optimization and modulo-counting problems.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info