● 摘要
最小顶点覆盖问题是理论计算机科学的核心基本问题之一，同时也是最基本的NP完全问题之一，对其难解性的认知和理解是探索“NP=P？”的重要途径，其求解方法、解的个数计算以及解空间的表示等一系列问题的研究在数学、物理学、计算机科学中都有着重要背景和意义。
本文从Vertex-Cover问题的节点相关性的统计分析入手，结合问题的结构特征，经过一系列严格的分析，解决了一些简单结构，如树、二分图等的minimum vertex-cover问题，得到了基于“摘叶”和“类最大匹配”的算法。总体而言，论文利用摘叶算法对节点排序，分析节点的结构特征和相关性从而化简得到顶点覆盖问题的解空间，并用图形的方式表示出解空间，然后进行统计分析和计算。首先，借助这一思路，在树状图、lattice上，得到了严格的解空间结构，包括确定性节点和自由节点，在此基础上进行了解的个数的探索和计算；在二分图结构上，论文综合利用了最大匹配和最小覆盖之间的关联关系，通过最大匹配构建节点间的相关性关系，建立了针对一般二分图的最小顶点覆盖解空间的刻画方法，并进行了严格理论分析；此外，论文严格分析了该算法在一般图上的表现，并给出了相关的复杂性分析；最后，结合层级中心性的概念，给出了优化该算法的启发式策略。
相比于现有的算法，这一新的算法在系综对称的情况下具有很好的效率，但是对于系综对称破缺的情况，算法仍然表现不足。这一算法提供了一个全新的视角来解决最小顶点覆盖问题，它可以用图形的方式来刻画出解空间的结构，对于我们深入理解NP完全问题的难解性根源提供了新的方法和视角。