Independent set problem is a widely studied NP-hard problem in the area of graph theory and has important applications in many fields. Branch and reduce is widely used tool for obtaining exact solutions for NP-hard and NP-complete problem. The main idea of the approach is to solve the problem by fast reducing the size of it, then decomposing it into sub-problems, recursively solving the sub-problems. In order to speed the running time of the algorithm, it adds some rules to reduce the size of the problem. This paper designs an exact algorithm based on branch and reduce to solve maximum independent set problem, and obtains the worst-case time running of the algorithm that is O(1.285n) . The results show that branch and reduce approach can get the exact solution of NP-hard problem in theory.%独立集问题是图论和组合数学中常见的NP-hard问题,在许多领域都有着重要的应用.分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一,主要通过快速降阶、分支及递归求解原问题及其子问题.针对图论中最大独立集问题设计了一个分支降阶算法,并通过增加快速降阶规则来降低算法的时间复杂度,最终通过分析得出一个时间复杂度为O(1.285n)的精确算法,该算法在理论上得到了一般图的最大独立集的最优解.
展开▼
