Abstract: Minimum vertex cover set problem is a well-known NP-Hard problem in the area of combinatorial optimization and has important applications in many fields. The analytical technology of Measure and Conquer is widely used to analyze the worst-case running time of exact algorithms based on branch and reduce. The main idea of Measure and Conquer is focused on choosing a refined non-standard measure to measure the size of the problem and its sub-problems at the each branching phase. In this work, we first use the technology of Branch and Reduce to design an exact algorithm for the minimum vertex cover problem, then use two kinds of methods to analyze the worst-case time complexity of the algorithm. We improve the worst-case time complexity of the same algorithm from O(1.325n) to O(1.255n) by employing the method of Measure and Conquer. The results of this work indicate that Measure and Conquer approach can significantly speed up exact algorithms and has wide applications in the analysis of exact algorithms.

Key words: graph theory, algorithm complexity, Measure and Conquer, Bbranch and Reduce, Minimum Vertex cover

摘要： 最小顶点覆盖问题是组合优化中经典NP-Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255ⁿ),优于常规分析下的时间复杂度O(1.325ⁿ) 。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。

关键词: 图论, 算法复杂性, 加权分治技术, 分支降阶技术, 最小顶点覆盖