20 2016，52（1） Computer Engineering and Applications 计算机工程与应用 图论中最大独立集问题的精确算法 陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍 CHEN Jizhen, NING Aibing, ZHI Zhibing, HU Linlin, ZHANG Huizhen 上海理工大学 管理学院，上海 200093 School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China CHEN Jizhen, NING Aibing, ZHI Zhibing, et al. Exact algorithm for maximum independent set problem in graph theory. Computer Engineering and Applications, 2016, 52（1）：20-22. Abstract：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. Key words：graph theory; maximum independent set; branch and reduce; exact algorithm 摘 要：独立集问题是图论和组合数学中常见的 NP-hard 问题，在许多领域都有着重要的应用。分支降阶是目前广 泛用于设计精确算法求解 NP-hard 问题的技术之一，主要通过快速降阶、分支及递归求解原问题及其子问题。针对 图论中最大独立集问题设计了一个分支降阶算法，并通过增加快速降阶规则来降低算法的时间复杂度，最终通过分 析得出一个时间复杂度为 O(1.285n) 的精确算法，该算法在理论上得到了一般图的最大独立集的最优解。 关键词：图论；最小顶点覆盖；快速降阶；精确算法 文献标志码：A 中图分类号：O223 doi：10.3778/j.issn.1002-8331.1503-0144 1 引言 （1）自 20世纪 60年代初，现代图的支配集及独立集[1-2] 概念被首次提出至今，独立集、支配集及其各种变形问 题 在 图 论 、组 合 数 学 、计 算 机 科 学 等 领 域 被 广 泛 的 研 究。该类问题在市场分析、方案选择、信号传输、计算机 视觉、故障诊断等领域具有非常广泛的应用[3]，因此具有 极其重要的研究价值和意义。人们在自独立集提出之 际就认识到除非 P = NP ，否则不存在多项式时间算法； 因此目前求解该类问题的算法主要分为精确算法和启 发式算法。 （2）精确算法有着悠久的历史，如运筹学中的动态 规划法、分支法、回溯法、递归法[4]等，虽然大量学者提出 了多种精确算法来求解最大独立集问题[5-8]，但随着问题 规模和图中结点总规模的增大，求解该问题的时间复杂 度也越来越高。 （3）20 世纪 80 年代末，学者们开始尝试运用启发式 算法 [9-15]来求解最大独立集问题，并且取得了比较满意 的效果，但运用启发式算法最大的缺点在于无法得到该 类问题的最优解。 （4）为了在获得该类问题最优解的同时降低算法的 基金项目：国家自然科学基金（No.71401106）；上海市一流学科建设项目（No.S1201YLXK）；高等学校博士学科点专项科研基金联 合资助课题（No.20123120120005）。 作者简介：陈吉珍（1990—），女，硕士生，研究方向为算法、物流工程，E-mail：chenjizhen4545@163.com；宁爱兵（1972—），男，博士， 副教授，研究方向为算法设计、系统工程；支志兵（1990—），男，硕士生，研究方向为算法、系统工程；胡琳琳（1993—）， 女，硕士生，研究方向为算法、物流工程；张惠珍（1979—），女，博士，副教授，主要研究方向为优化算法。 收稿日期：2015-03-15 修回日期：2015-08-03 文章编号：1002-8331（2016）01-0020-03 CNKI 网络优先出版：2015-08-20, http://www.cnki.net/kcms/detail/11.2127.TP.20150820.1641.007.html 

陈吉珍，宁爱兵，支志兵，等：图论中最大独立集问题的精确算法 2016，52（1） 21 时间复杂度，需要对所求问题增加更多快速降阶的规 则。本文求解最大独立集问题所运用的方法是分支和 递归相结合的分支降阶算法 [16-17]，其核心思想在于首先 通过分析给出问题的性质，对原问题进行快速降阶；其 次在无法依据问题性质进行快速降阶时对原问题进行 分支求解；最后对分支后的问题进行递归求解。 2 基础知识 2.1 符号及术语 为方便描述，本文采用如下符号来表示。 G = (VE) ：G 代表图，V、E 分别代表该图的结点集 和边集； n ：图中的结点数量； N (v) ：表示结点 v 的开邻集，即所有与结点 v 之间 存在一条边的点集合； N [v] ：表示结点 v 的闭邻集，即 N (v)  {v} ； d(v) ：点 v 的度，即与点 v 相关联的边的数目。 设 G 1 Í V ，E 1 E = (V ) 为图 G 导出子图并记为 G[V ] ，其中 1 1 1 Í E 且 E 中顶点所组成的边。 1 是由 V 1 V 1 通常用大写字母表示集合，用小写字母表示集合中 的某一元素。 2.2 求解算法时间复杂度的通用公式 设基于分支降阶的递归算法得到如下的递推公式： ) ，其 中 n 为 原 问 ) 分别为第 12r ) +  + T (n - k )(n - k r T (n) = T (n - k ) + T (n - k 1 2 )(n - k 题的规模；(n - k 1 个子问题的规模。 2 r x 令 T (n) = x + x n +  + x ，则上述递推式可以转化为求方程 x = 的唯一或者最大解。设方程唯一 n 2 n - k n - k n - k 1 或最大解为 α ，则该算法其最坏情况下的时间复杂度为 ) 。该方法的详细信息请参考文献[8]和文献[12]。 O(α r n 3 最大独立集问题的性质及其证明 设任意给定简单无向图 G = (VE) ，其中 V 表示顶点 集，E 表示边集；最大独立集 MIS（Maximum Independent Set）集合 S（其中 S Í V ）中任意两个结点都互不相连， 且 S 中元素个数最多。 性质 1 对于任意一个独立集 S 内的任意顶点 v 都 满足 N [v]  S = Æ 。 证明 根据最大独立集定义显然成立。 性质 2 S 中的任意两个元素之间都是 2 阶或以上 的邻接结点。 证明 根据性质 1 显然成立。 性质 3 图中任意度为 0 的顶点，必定包含在最大独 立集中。 证 明 因 为 任 意 一 个 度 为 0 的 顶 点 都 是 一 个 孤 立 点，加入最大独立集中显然可以增加最大独立集 S 的规 模并且不会影响到其他顶点。 性质 4 图中全是顶点的度都为 1，则该图必然是 n 条孤立的直线，直线两端为其顶点，则任意一条直线必 须取而且只能取一个顶点加入最大独立集中，并且问题 可以在多项式时间内解决。 证明 根据性质 1 和性质 3 显然成立。 性质 5 若图 G 中所有结点的度数都小于等于 2，则 该问题多项式时间内可求解。 证明 由性质 2 可以去掉度为 0 的所有结点，之后只 有以下两种情况： （1）图中只有两个度为 1 的结点，其他结点的度都为 2，此时实际上是一条简单路径，此时显然可以在多项式 时间内求解；并由此可以推出如若 N [v] Í N [u] ，则直接 将 u 排除出最大独立集中，同时称顶点 v 被顶点 u 支配。 （2）图中的所有结点度都为 2，此时实际上是一条简 单回路，显然也可以在多项式时间内求解。 性 质 6[18] 若 G 中 v 不 在 S 中 且 N [v] 并 非 全 部 相 连，则 N (v) 必有至少两个顶点在 S 中。 证明 由于顶点 v 不在最优解中，显然基于最大独 立集的定义，必然至少有一个邻接顶点在 S 中；如果仅 有一个邻接顶点在 S 中，那么显然将 v 加入 S 效果更 优，由此得出 N (v) 必至少有两个顶点在 S 中。 4 算法及时间复杂度分析 4.1 算法流程 根据以上性质，分支降阶算法先从度数较小的顶点 进行约简处理，由此可以设计出最大独立集的分支降阶 的递归算法，用自然语言描述算法如下。 算法 最大独立集 MIS(GS) 输入：图 G = (V E) ； 输出：一个最大独立集顶点子集 max(S) 。 1.初始化：输入一个 G ，并令此时最大独立集 S = Æ 。 2.如果 G 中有顶点的度 d(v) = 0 ，则返回 MIS(G - v S  v)。 3.如果 G 中有顶点的度 d(v) = 1，则返回 MIS(G - N [v] S  v)。 4.如果 d(v) = 2 ，分为以下两种情况讨论。 4.1. V 中所有顶点的度 d(w) = 2 ；显然可知 MIS|S| = |S|/2 。 )  3 ； 4.2.存在 N (v) 分别是 w ，w 1 则可分为以下两种情况讨论： )  3 或者 d(w 其中 d(w 1 2 2 4.2.1.点 w 1 和 w 相连，此时 v 被点 w 1 2 和点 w 2 所支配；根 据性质 5 可知；此时直接返回：MIS(G - N [u] S  v) 。 不相连，则分成以下两个子问题分别求解： 2 和 w 4.2.2.点 w 1 （1）MIS(G - N [u] S  v) ] S  w  w （2）MIS(G - N [w ] - N [w 1 1  w  w 5.如果 d(v) = 3 ，令 N (v) ={w 2 1 2 ) 2 情况进行讨论： 5.1.若 w 、w 1 、w 2 3 三个顶点之间互连，则返回：MIS(G - N [v] } ；则可分为以下几种 3 

22 2016，52（1） Computer Engineering and Applications 计算机工程与应用 S  v) 。 （3）算 法 5.2 步 的 时 间 复 杂 度 求 解 公 式 ：T (n) =  w 5.2.若 {(w 1  w )、(w 1 2 )Î E} 则分成以下两个子问题分别 3 T (n - 4) + T (n - 6) ，通过计算可以得出此时 c » 1.151 。 求解： （1）MIS(G - N [v] S  v) （2）MIS(G - N [w ] - N [w 3  w  w 同 理 {(w )、(w 2 1 2 2 ] S  w  w ) 2  w )Î E} 或 者 {(w 1 3 3  w )Î E} ， 2 3 这两种情况与前一种情况类似，所以此处不另做讨论。  w 5.3.若只有三个顶点之间只有一条边互连，以 (w 1 )、(w 3 )Î E 2 为例，则分为以下两种情况讨论。 5.3.1.如果存在点 w 1 支配点 w 2 根据性质 5 得，此时分成 以下两个子问题分别求解： （1）MIS(G - N [v] S  v) （2）MIS(G - N [w ] - N [w 1 5.3.2.如果上述条件不成立，则分成以下三个子问题分别 ] S  w 1 3  w ) 3 求解： （1）MIS(G - N [v] S  v) （2）MIS(G - N [w ] - N [w 1 （3）MIS(G - N [w ] - N [w 1 5.4.若三个顶点之间互不相连，因为三者互不相连所以不 可能存在某个顶点被其他顶点支配的状态，则分成以下四个 子问题分别求解： ] S  w 1 3 ] S  w  w ) 3  w )} 2 3 2 （1）MIS(G - N [v] S  v) （2）MIS(G - N [w ] - N [w 1 ] - N [w （3）MIS(G - N [w 1 2 （4）MIS(G - N [w ] - N [w 2 6.如果 d(v)  4 。 6.1.如果 G(V E) 中存在 d(w) 大于等于 5，则分为以下两 ] S  w  w 1 3  S  w ] - w 3 1  S  w ] - w 1 3 ) 3  w 2  w )} 3 ) 2 个子问题进行求解： （1）MIS(G(V - N [w]) S  w) （2）MIS(G(V - w) S)) 6.2.如果不存在此种情况，则 G 图中所有顶点都为 4，则 任取一顶点进行一次分支后，可直接返回步骤 4 即可。 7.比较所有求出的集合 S ，并输出 max(S) ，算法结束。 4.2 时间复杂度分析 下面依据时间复杂度分析技术对上述算法的时间 复杂性进行分析。本文采用算法是基于分支降阶算法， 因此可以根据求解分支降阶情况下的时间复杂度的通 项公式 T (n) = T (n - j) + T (n - k) 求解出此类问题的时间 复杂度。 根据第 3 章的性质及 4.1 节的算法，显然可以得出 以下结论：算法步骤 1、2、3、4.1、4.2.1 在多项式时间内即 可完成。求解分支降阶情况下的时间复杂度的通项公 式 T (n) = T (n - j) + T (n - k) ，可以根据算法的具体步骤进 行下列分析。 （4）算 法 5.3.1 步 的 时 间 复 杂 度 求 解 公 式 ：T (n) = T (n - 4) + T (n - 6) ，通过计算可以得出此时 c » 1.151 。 （5）算 法 5.3.2 步 的 时 间 复 杂 度 求 解 公 式 ：T (n) = T (n - 4) + T (n - 6) + T (n - 6) ，通过计算可以得出 c » 1.272。 （6）算 法 5.4 步 的 时 间 复 杂 度 求 解 公 式 ：T (n) = T (n - 4) + T (n - 6) + T (n - 7) + T (n - 7)，通过计算可以得出 c » 1.282。 （7）算 法 第 6 步 的 时 间 复 杂 度 求 解 公 式 为 T (n) = T (n - 1) + T (n - 6) ，通过计算可以得出此时 c » 1.285 。 综合上述分析可以得出一般图的最大独立集算法 最坏情况下的时间复杂度 O(1.285n) 。 5 结束语 主要研究了最大独立集问题的性质和解决该问题 的算法及算法的时间复杂度。首先通过分析该问题的 性质，然后设计出一个基于分支降阶技术的递归算法， 并应用常规技术分析算法时间复杂度，得出该算法的时 间复杂度为 O(1.285n) ，在理论上求解出了该问题的最 优解。同时本文的性质可以在一定程度上降低原问题 的求解规模与难度，因此也可以结合启发示算法对该问 题进行求解，达到加快最大独立集问题求解速度与提高 求解效果的目的。 参考文献： [1] Haynes T W，Hedetniemi S，Slater P.Fundamentals of dom- ination in graphs[M].[S.l.]：CRC Press，1998. [2] Gavril F.Algorithms for minimum coloring，maximum clique， minimum covering by cliques，and maximum independent set of a choral graph[J].SIAM Journal on Computing，1972， 1（2）：180-187. [3] 王丽爱，周旭东，陈崚.最大团问题研究进展及算法测试标 准[J].计算机应用研究，2007，24（7）：69-70. [4] 王晓东.计算机算法设计与分析[M].3 版.北京：电子工业出 版社，2007. [5] 肖鸣宇，陈建二，韩旭里.低度图的点覆盖和独立集问题下 界改进[J].计算机学报，2005，28（2）：153-160. [6] Robson J M.Finding a maximum independent set in time O(2n/4)，Technical Report 1251-01[R].LaBRI，Université de Bordeaux I，2001. [7] 路纲，周明天，唐勇，等.任意图支配集精确算法回顾[J].计 算机学报，2010，33（6）：1073-1087. （1）算 法 4.2.2 步 的 时 间 复 杂 度 求 解 公 式 ：T (n) = [8] Fomin F V，Kratsch D.Exact exponential algorithms[M]. T (n - 3) + T (n - 5) ，通过计算可以得出此时 c » 1.194 。 Berlin：Springer，2010. （2）算法 5.1 步在多项式时间内就可以解决。 （下转 109 页）