Meta-kernelization with structural parameters

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GANIAN Robert SZEIDER Stefan SLIVOVSKY Friedrich

Rok publikování 2016
Druh Článek v odborném periodiku
Časopis / Zdroj Journal of Computer and System Sciences
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://linkinghub.elsevier.com/retrieve/pii/S0022000015000914
Doi http://dx.doi.org/10.1016/j.jcss.2015.08.003
Klíčová slova Boolean-width; Clique-width; Kernelization; Modular decomposition; Monadic second-order logic; Parameterized complexity; Rank-width
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.