最小顶点覆盖问题的加权分治算法

Measure and Conquer Approach for the Minimum Vertex Cover Problem

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

Minimum vertex cover set problem is a well-known NP-Hard problem in the area of combinatorial opti- mization 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 cations in the analysis of exact algorithms. can significantly speed up exact algorithms and has wide appli-cations in the analysis of exact algorithms.