Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Ganian, R., Slivovsky, F., & Szeider, S. (2016). Meta-kernelization with structural parameters. Journal of Computer and System Sciences, 82(2), 333–346. https://doi.org/10.1016/j.jcss.2015.08.003
E192-01 - Forschungsbereich Algorithms and Complexity
-
Journal:
Journal of Computer and System Sciences
-
ISSN:
0022-0000
-
Date (published):
2016
-
Number of Pages:
14
-
Peer reviewed:
Yes
-
Keywords:
Applied Mathematics; Theoretical Computer Science; Computational Theory and Mathematics; Computer Networks and Communications
-
Abstract:
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 Cbe an arbitrary but fixed clas...
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 Cbe an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the C-cover numberof 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 C. 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 C-cover number. We provide similar results for MSO expressible optimization and modulo-counting problems.
