图论中最大独立集问题的精确算法-陈吉珍

ComputerEngineeringandApplications计算机工程与应用2016，52（1）1引言（1）自20世纪60年代初，现代图的支配集及独立集[1-2]概念被首次提出至今，独立集、支配集及其各种变形问题在图论、组合数学、计算机科学等领域被广泛的研究。该类问题在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用[3]，因此具有极其重要的研究价值和意义。人们在自独立集提出之际就认识到除非P=NP，否则不存在多项式时间算法；因此目前求解该类问题的算法主要分为精确算法和启发式算法。（2）精确算法有着悠久的历史，如运筹学中的动态规划法、分支法、回溯法、递归法[4]等，虽然大量学者提出了多种精确算法来求解最大独立集问题[5-8]，但随着问题规模和图中结点总规模的增大，求解该问题的时间复杂度也越来越高。（3）20世纪80年代末，学者们开始尝试运用启发式算法[9-15]来求解最大独立集问题，并且取得了比较满意的效果，但运用启发式算法最大的缺点在于无法得到该类问题的最优解。（4）为了在获得该类问题最优解的同时降低算法的图论中最大独立集问题的精确算法陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍CHENJizhen,NINGAibing,ZHIZhibing,HULinlin,ZHANGHuizhen上海理工大学管理学院，上海200093SchoolofManagement,UniversityofShanghaiforScienceandTechnology,Shanghai200093,ChinaCHENJizhen,NINGAibing,ZHIZhibing,etal.Exactalgorithmformaximumindependentsetproblemingraphtheory.ComputerEngineeringandApplications,2016,52（1）：20-22.Abstract：IndependentsetproblemisawidelystudiedNP-hardproblemintheareaofgraphtheoryandhasimportantapplicationsinmanyfields.BranchandreduceiswidelyusedtoolforobtainingexactsolutionsforNP-hardandNP-completeproblem.Themainideaoftheapproachistosolvetheproblembyfastreducingthesizeofit,thendecomposingitintosub-problems,recursivelysolvingthesub-problems.Inordertospeedtherunningtimeofthealgorithm,itaddssomerulestoreducethesizeoftheproblem.Thispaperdesignsanexactalgorithmbasedonbranchandreducetosolvemaximumindependentsetproblem,andobtainstheworst-casetimerunningofthealgorithmthatisO(1.285n).TheresultsshowthatbranchandreduceapproachcangettheexactsolutionofNP-hardproblemintheory.Keywords：graphtheory;maximumindependentset;branchandreduce;exactalgorithm摘要：独立集问题是图论和组合数学中常见的NP-hard问题，在许多领域都有着重要的应用。分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一，主要通过快速降阶、分支及递归求解原问题及其子问题。针对图论中最大独立集问题设计了一个分支降阶算法，并通过增加快速降阶规则来降低算法的时间复杂度，最终通过分析得出一个时间复杂度为O(1.285n)的精确算法，该算法在理论上得到了一般图的最大独立集的最优解。关键词：图论；最小顶点覆盖；快速降阶；精确算法文献标志码：A中图分类号：O223doi：10.3778/j.issn.1002-8331.1503-0144基金项目：国家自然科学基金（No.71401106）；上海市一流学科建设项目（No.S1201YLXK）；高等学校博士学科点专项科研基金联合资助课题（No.20123120120005）。作者简介：陈吉珍（1990—），女，硕士生，研究方向为算法、物流工程，E-mail：[e-mail]；宁爱兵（1972—），男，博士，副教授，研究方向为算法设计、系统工程；支志兵（1990—），男，硕士生，研究方向为算法、系统工程；胡琳琳（1993—），女，硕士生，研究方向为算法、物流工程；张惠珍（1979—），女，博士，副教授，主要研究方向为优化算法。收稿日期：2015-03-15修回日期：2015-08-03文章编号：1002-8331（2016）01-0020-03CNKI网络优先出版：2015-08-20,，52（1）时间复杂度，需要对所求问题增加更多快速降阶的规则。本文求解最大独立集问题所运用的方法是分支和递归相结合的分支降阶算法[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相关联的边的数目。设G1=(V1E1)为图G导出子图并记为G[V1]，其中V1ÍV，E1ÍE且E1是由V1中顶点所组成的边。通常用大写字母表示集合，用小写字母表示集合中的某一元素。2.2求解算法时间复杂度的通用公式设基于分支降阶的递归算法得到如下的递推公式：T(n)=T(n-k1)+T(n-k2)++T(n-kr)，其中n为原问题的规模；(n-k1)(n-k2)(n-kr)分别为第12r个子问题的规模。令T(n)=xn，则上述递推式可以转化为求方程xn=xn-k1+xn-k2++xn-kr的唯一或者最大解。设方程唯一或最大解为α，则该算法其最坏情况下的时间复杂度为O(αn)。该方法的详细信息请参考文献[8]和文献[12]。3最大独立集问题的性质及其证明设任意给定简单无向图G=(VE)，其中V表示顶点集，E表示边集；最大独立集MIS（MaximumIndependentSet）集合S（其中SÍV）中任意两个结点都互不相连，且S中元素个数最多。性质1对于任意一个独立集S内的任意顶点v都满足N[v]S=Æ。证明根据最大独立集定义显然成立。性质2S中的任意两个元素之间都是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。4.2.存在N(v)分别是w1，w2其中d(w1)3或者d(w2)3；则可分为以下两种情况讨论：4.2.1.点w1和w2相连，此时v被点w1和点w2所支配；根据性质5可知；此时直接返回：MIS(G-N[u]Sv)。4.2.2.点w1和w2不相连，则分成以下两个子问题分别求解：（1）MIS(G-N[u]Sv)（2）MIS(G-N[w1]-N[w2]Sw1w2)5.如果d(v)=3，令N(v)={w1w2w3}；则可分为以下几种情况进行讨论：5.1.若w1、w2、w3三个顶点之间互连，则返回：MIS(G-N[v]陈吉珍，宁爱兵，支志兵，等：图论中最大独立集问题的精确算法21ComputerEngineeringandApplications计算机工程与应用2016，52（1）Sv)。5.2.若{(w1w2)、(w1w3)ÎE}则分成以下两个子问题分别求解：（1）MIS(G-N[v]Sv)（2）MIS(G-N[w3]-N[w2]Sw3w2)同理{(w1w2)、(w2w3)ÎE}或者{(w1w3)、(w2w3)ÎE}，这两种情况与前一种情况类似，所以此处不另做讨论。5.3.若只有三个顶点之间只有一条边互连，以(w1w2)ÎE为例，则分为以下两种情况讨论。5.3.1.如果存在点w1支配点w2根据性质5得，此时分成以下两个子问题分别求解：（1）MIS(G-N[v]Sv)（2）MIS(G-N[w1]-N[w3]Sw1w3)5.3.2.如果上述条件不成立，则分成以下三个子问题分别求解：（1）MIS(G-N[v]Sv)（2）MIS(G-N[w1]-N[w3]Sw1w3)（3）MIS(G-N[w1]-N[w2]Sw3w2)}5.4.若三个顶点之间互不相连，因为三者互不相连所以不可能存在某个顶点被其他顶点支配的状态，则分成以下四个子问题分别求解：（1）MIS(G-N[v]Sv)（2）MIS(G-N[w1]-N[w3]Sw1w3)（3）MIS(G-N[w1]-N[w2]-w3Sw1w2)（4）MIS(G-N[w2]-N[w3]-w1Sw2w3)}6.如果d(v)4。6.1.如果G(VE)中存在d(w)大于等于5，则分为以下两个子问题进行求解：（1）MIS(G(V-N[w])Sw)（2）MIS(G(V-w)S))6.2.如果不存在此种情况，则G图中所有顶点都为4，则任取一顶点进行一次分支后，可直接返回步骤4即可。7.比较所有求出的集合S，并输出max(