کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429775 | 687672 | 2016 | 14 صفحه PDF | دانلود رایگان |
• Kernelization meta-algorithms parameterized by structural graph parameters.
• Preprocessing for MSO definable decision, optimization and counting problems.
• Parameter based on a combination of rank-width and modular decompositions.
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 CC be an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the CC-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 CC. 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 CC-cover number. We provide similar results for MSO expressible optimization and modulo-counting problems.
Journal: Journal of Computer and System Sciences - Volume 82, Issue 2, March 2016, Pages 333–346