Research On Kernelization For Sparse-Hereditary Graph Problems

Sparse-Hereditary Graphs is an important graph class which contains many other graph classes, such as d-degenerate Graphs, Graphs with Bounded Arboricity, Graphs with Bounded Degree, Graphs with Bounded Genus and Planar Graphs which have significant theoretical and practical research values. In this paper, we mainly focus on the kernelization for FPT (Fixed-Parameter Tractability) problems on Sparse-Hereditary Graphs with sparseness smaller than 3.We first study the kernelization for cover problems restricted to Sparse-Hereditary Graphs with constrained low-degree vertices. By doing researches on the relation of low-degree vertices and the solution space properties of these problems, we show that these problems admit a kernel of size O(f(k)2), where f(k) is a computable function relate to a solution of this problem. Base on this result, a general method (low-degree vertices bonding method) to design kernels for Sparse-Hereditary Graph problems is proposed. Base on the proposed kernelization method, the connected vertex cover, tree cover, tour cover and edge dominating set problems on Sparse-Hereditary Graphs with sparseness smaller than 3 are studied.The connected vertex cover problem is studied firstly. By thorough study on combinatorical structures of the problem, a group of efficient reduction rules. Instances of connected vertex cover are translated to a certain cover problem restricted to Sparse-Hereditary Graphs with constrained low-degree vertices by these reduction rules, and a kernel of size (6-a)k/(3-a), where 0