Meta-kernelization with structural parameters
| Autoři | |
|---|---|
| Rok publikování | 2016 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Computer and System Sciences |
| Fakulta / Pracoviště MU | |
| 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: |