顶点覆盖问题线性内核算法

Linear Kernelization Algorithm for the Vertex Cover Problem

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).

Parameterized complexity as a branch of the algorithm research gets more worldwide attention recent years. Linear kernel as the important field in research of Parameterized Complexity is widely studied by computer scientists. In this paper, a linear kernel algorithm of the vertex cover problem is given and the correctness of the algorithm is also shown and it is a first proof of linear kernel in China. The following is a brief description of the algorithm. First, a 2-approximation algorithm of the vertex cover problem is used to get two sets of vertices A and B, and then many reduction rules are used to get a new graph, and it is shown that the original graph has vertex cover of size k if and only if the new graph has vertex cover of size k′. Finally, it is proved that the total number of the vertices in the new graph is bounded by 2k, which means a linear kernel, and 2k is the lower bound of this problem.