顶点覆盖k-路问题

The vertex cover problem is one of the most classical NP-hard problems in combinatorial optimization and computer science. Erd?s (International Mathematician, Wolf Prize winner) and other scientists generalized it into the vertex cover certain types of subgraph problems. The generalized problems, closely correlating with approximation algorithm theory and computational complexity theory, are the hot research topics in graph theory in recent two decades. The vertex cover k-path problem is one of the generalized problems. And, the study on the vertex cover k-path problem also has important links with other topics of graph theory. Meanwhile, the vertex cover k-path problem can be applied on two important real cases. .This project will study the vertex cover k-path problem from two aspects. First, from the algorithmic perspective, we will determine the algorithmic complexity of some problems and give approximation algorithms or polynomial time exact algorithms. In general cases, we will design some approximation algorithms for the vertex cover k-path problem which work for any integer k. On the other hand, we want to get some results on the vertex cover k-path number. We plan to combine the classical method in graph theory and the probabilistic method to find the relationships between the vertex cover k-path number and the other invariants (maximum degree, diameter, radius, girth etc.). We will try to figure out the exact vertex cover k-path number for some graphs, if we can't find good methods to get the exact number, we will try to give some better upper and lower bounds of the vertex cover k-path number.

顶点覆盖问题是组合优化和计算机科学领域最经典NP难问题之一，Erd?s(国际数学大师，Wolf 奖得主)等人把它推广成了顶点覆盖某类子图问题。这类推广问题，与近似算法理论和计算复杂性理论有着紧密联系，是近二十年来图论研究的热点问题。顶点覆盖k-路问题也属于这类推广的问题。同时，顶点覆盖k-路问题的研究，与图论的其他课题也有着重要联系，且在两类实际问题中有着重要应用。. 本项目将从两个方面来研究顶点覆盖k-路问题。首先，我们从算法的角度研究顶点覆盖k-路问题，确定某些问题的算法复杂性，给出这些问题的近似算法或多项式时间的精确算法。设计k为一般情况下的顶点覆盖k-路问题的近似算法。另一方面，我们研究顶点覆盖k-路数。将经典图论中的方法与概率方法相结合，来研究图的顶点覆盖k-路数与图的若干其他不变量（最大度、直径、半径、围长等）的关系，给出图的顶点覆盖k-路数的上下界，或者精确值。

本项目研究的主要问题是顶点覆盖k-路问题：在给定图G中找一个最小的顶点子集F，使得图中任何一条k个顶点的路都至少有一个顶点在这个顶点子集F中。它是经典的顶点覆盖问题的推广，同时也属于Erdos（Wolf奖得主）等人推广的顶点覆盖子图问题，故此问题的研究在计算机算法与复杂性方面有着重要的理论意义。同时顶点覆盖k-路问题的研究在实际中也有着广泛的应用，特别是在无线传感器网络加密问题与交通灯设置问题上有着重要应用。由此，顶点覆盖k-路问题吸引了越来越多的国内外学者的关注，已经成为图论与计算机算法领域的一个研究热点。. 项目主要从算法的角度重点研究了顶点覆盖k-路问题，研究了一般图上的顶点覆盖k-路问题近似算法以及特殊图上问题的计算复杂性与求解算法。目前，项目组得到的主要结果有：. （1）证明了对于任意的k>=2，顶点覆盖k-路问题都是NP-完全的，并利用原始对偶方法与局部比值法给出了一般图上顶点赋权情况下顶点覆盖3-路问题的两个2-近似算法，这也是顶点覆盖3-路问题近似算法方面最好的结果；. （2）研究了特殊图上的顶点覆盖k-路问题，证明了顶点覆盖3-路问题与顶点覆盖4-路问题在三正则图上都是NP-完全的，并分别给出了1.25-近似算法与2-近似算法；. （3）研究了树、单圈图、仙人掌图上的顶点覆盖k-路问题，并给出了这些图上的多项式时间的精确算法；. （4）考察了顶点覆盖k-路问题的参数化算法，用迭代压缩方法分别给出了顶点覆盖3-路问题与顶点覆盖4-路问题的固定参数算法；. （5）研究了相关的组合优化问题：部分顶点覆盖问题与奖励收集的顶点覆盖问题，对这两个问题给出了目前最好的近似算法，以及研究了其他的一些图论问题，得到一些研究成果。