Kernelization For NP-hard Problems On Graphs With Small Distance Property

There is no exact algorithm runing in polynomial time for NP-Hard problems in graphs, unless P=NP. Researches about NP-hard problems mainly focus on parameter?ized algorithms, approximation algorithms, heuristic algorithms, exact algorithms, etc.As a significant part of parameterized algorithms, kernelization not only can be used to improve parameterized algorithms, but also can work as a preprocess when solving NP-hard problems.A kernelization algorithm takes an instance (G, k) of a parameterized problem Q as input, and applies a set of polynomial-time executable data reduction rules to shrink the size of G, resulting in an equivalent instance (G', k'). Hereby, (G, k) is a yes-instance if and only if (G', k') is a yes-instance, k' ? k, and the size of G' is bounded by a function g(k). The function g(k) is called as the kernel of this problem. Since most of problems has a small parameter k in applications, it often admits a small kernel, which can be solved quickly even by brute force algorithms.Besides excellent performance in practice, kernelization has a guarantee in theroy,which ensures its equivalence to the original problem. Therefore, kernelization algo-rithm can also work as a preprocessing step of approximation algorithms, heuristic algo-rithms and exact algorithm, and kernelization algorithms evenly get optimal solution in some cases. Since a problem admits a problem kernel if and only if it is fixed-parameter tractable, we often take kernelization as a technique to design parameterized algorithms.This article firstly studies some kernelization technique, and gives a new idea to design kernelization algorithm which combines "crown decomposition" with "region de-composition" techniques and generalizes them. We design some kernelization algorithms for ALMOST INDUCED MATCHINNG problem and 3-PATH VERTEX COVER problem in graphs to get a kernel of size 8k and 5k, respectively. It firstly finds a special partition of vertices by local adjusting rules, and bounds the size of each part. If the size of graph is grater than a given bound, we can either solve the problem, or find a "crown-similar structure",which can reduce the size of the graph. Otherwise, we get a kernel of the problem. These two kernels beat all previous results.In addition, we propose a new frame to find better kernels for a group of problems in graphs that admit a "small distance" property. As two applications of this frame,the kernelization algorithms we proposed above get better theory bounds. This frame is applicable for many other problems, which gives an idea to get better kernels for other problems.