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

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

陈吉珍，宁爱兵，支志兵，王永斐，张惠珍

(上海理工大学管理学院，上海200093)

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

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

收稿日期：2014-11-04

基金项目：国家自然科学基金(71401106);上海市一流学科建设项目资助(S1201YLXK); 高等学校博士学科点专项科研基金联合资助课题(20123120120005)

作者简介：陈吉珍(1990-)，女，硕士生，研究方向为算法、物流工程；宁爱兵(1972-)，男，博士，副教授，研究方向为算法设计、系统工程；支志兵(1990-)，男，硕士生，研究方向为算法、系统工程；王永斐(1988-)，男，硕士生，研究方向为算法、系统工程；张惠珍(1979-)，女，博士，副教授，研究方向为优化算法。

中图分类号：O223文章标识码：A

Measure and Conquer Approach for the Minimum Vertex Cover Problem

CHEN Ji-zhen，NING Ai-bing，ZHI Zhi-bing，WANG Yong-fei，ZHANG Hui-zhen

(SchoolofManagement,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

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

0引言

顶点覆盖问题[1]及其各种变形问题在图论、组合数学、运筹学、管理及计算机科学等领域被广泛的研究。最小顶点覆盖(minimum vertex cover , 以下简称MVC)问题是顶点覆盖问题中最常见、研究最多及应用最广的一种，也是组合优化中典型NP-Hard问题，除非P=NP,否则不存在多项式时间算法。人们对MVC问题的精确算法、近似算法和启发示算法做了大量研究[2～6]。近年来，由于加权分治分析技术[7～11]的提出，基于加权分治技术的精确算法[12,13]的设计和分析被广泛应用于求解NP-Hard问题中，以期求得精确解的同时，获得更好更逼近的时间上界；其核心思想可以理解为根据问题不同特征设置一组相应的权值，其目标就是尽可能提高算法的效率及降低算法的时间复杂度。

本文第1节给出了MVC问题的定义及其性质和证明；第2节根据定义和性质设计出基于分支降阶的递归算法，并对算法进行常规分析得出时间复杂度为O(1.325n)，同时运用加权分治技术进行复杂度分析，得出其时间复杂度为O(1.255n)；最后对本文研究内容加以总结并提出进一步的研究方向。

1最小顶点覆盖问题的定义及性质

设任意给定简单无向图G=(V,E)，其中V表示顶点集，E表示边集；S表示MVC的顶点集；|S|表示集合S的个数；d表示任意顶点v的度；N(v)={h|(v,h)∈E}表示顶点v的一阶开领域；N[v]=N(v)∪v表示顶点v的一阶闭邻域；N2(v)表示顶点v的二阶领域，即N(v)的邻接顶点，且不包括v本身。

定义：最小顶点覆盖，即任意给定的无向图G=(V,E)，求解一个最少顶点个数集合S使得任意边e=(u,v)∈E,有u∈S或v∈S,也就是S中的顶点覆盖了边集E。

性质1：任取一条属于G图中的边E=(vi,vj)，并定义M={vi,vj};则对于最小顶点覆盖的顶点集S都满足M∩S≠Ø。

证明：根据最小顶点覆盖集定义显然成立。

性质2：图中任意顶点vi,如果d(vi)=0，那么vi必定不包含在S中。

证明：因为度为的0顶点都是一个孤立点，不加入S显然不会影响到其它顶点且满足顶点覆盖的要求。

性质3：若图G中任意顶点vi的度d(vi)=1，则该图必然是n条孤立的直线，直线两端为其顶点，则任意一条直线必须只取一个顶点加入S中，显然问题可以在多项式时间内解决。

证明：显然成立，否则与所求问题相矛盾。

性质4：若图G中任意顶点vi的度d(vi)≤ 2，则该问题多项式时间内可求解。

证明：由性质2可以去掉所有度为0的顶点，之后只有以下2种情况：

(1)图中既有度为1也有度为2的顶点，则任取一个d(vi)=1的顶点vi,直接删除，并将N(vi)加入S，直到图中不存在度为1的顶点，此时显然可以在多项式时间内求解。

(2)图中的所有顶点度都为2，此时实际上是一条或多条简单回路，此时显然也可以在多项式时间内求解。

性质5[14]：若图G中顶点vi的度d(vi)=2，如果其邻接顶点w1与w2之间不相连，则删除图中的顶点v,w1,w2并由一个新顶点v*代替，同时把原来联结到w1和w2的所有边联结到新增点v*上。新加入的点v*在取得V*后按下面的规则处理。

(1) 若最终的S中包含点v*, 则S=S-{v*} + {w1,w2};

(2) 若最终的S中不包含点v*, 则S=S-{v*} +{v}。

证明：(1)如果最终的S中包含v*，那么证明边E(v*)中有一些边必须要v*来覆盖，故此w1,w2至少有一个在S中，同时为了覆盖边(v,w1)和边(v,w2)则应该另加入一个顶点，因此应该加入w1,w2最佳。(2)若最终的S中不包含v*，那么证明边E(v*)中已被其它顶点覆盖，此时只需将v加入S中即可。

性质6：若图G中存在N[v]⊆N[u],则直接将顶点v排除出S并将顶点u加入S中，同时称顶点v被顶点u所支配。

证明：显然由于顶点u能够支配顶点v所支配的所有边，因此将顶点u加入S的效果要比将顶点v加入S的效果更好。

2最小顶点覆盖问题的算法及复杂性分析

2.1最小顶点覆盖问题的算法

根据本文第2节的定义及性质，我们可以将度为0，1，2的顶点进行约简处理，由此我们可以设计出MVC问题基于分支降阶的递归算法，用自然语言描述算法如下。

算法: MVC(G,S)

输入:图G=(V,E)

输出：一个最小顶点覆盖集S，记为min(S)。

Step 1初始化：输入一个G,此时S=Ø;

Step 2找出图G中度为0的顶点集合V0，根据性质1，直接令V=V-V0，即从图G中删除顶点集合V0;

Step 3如果图G中存在顶点v∈V,且d(v)=1,N(v)=u,根据性质4，直接令V=V-v-u，S=S∪u，即从图G中删除顶点v,u，同时删掉v,u所关联的边，并将u加入S中；

Step 4存在顶点v∈V,且d(v)=2,N(v)={w1,w2},则可分为以下两种情况讨论：

Step 4.1如果{w1,w2}∈E，此时v被点w1和点w2所支配；根据性质5可知；此时直接令V=V-v-w1-w2，S=S∪w1∪w2，即从图G中删除顶点u,w1,w2，同时删掉u,w1,w2所关联的边，并将w1,w2加入S中；

Step 4.2如果{w1,w2}∉E，此时根据性质5此时直接返回G(V*，S)

Step 5如果存在顶点v∈V,且d(v)≥3，则分以下两种情况：

Step 5.1如果G图中所有顶点vi都等于3，则任意选取一个顶点进行一次分支后，可直接返回Step2即可。

Step 5.2选取G(V,E)中度最大的顶点v∈V,显然d(v)≥4,返回:MVC{G(V-v),S∪w;G(V-N[v]),S∪N(v)]}

Step 6输出min (S),算法结束。

2.2传统分析方法的时间复杂性

下面我们依据传统技术对上述算法的时间复杂性进行分析,根据2.1节中算法MVC(G,S)可知当图中度小于等于2可以直接约简，在多项式时间内求出；同时当最大度为3时也可以在多项式时间内求出，所以此处所求的图的任一顶点的度都大于等于3,且最大度大于3。因此令顶点个数n为问题的规模，T(n)为搜索树产生的叶子顶点个数，由此我们可以得出递推通项式：T(n)=T(n-1)+T(n-d-1)。

设T(n)=cn，其中c为待求解的常数，则cn=cn-1+cn-k由此我们可以得出ck=ck-1+1，其中k=d(vi)+1就可求得c，并得出其时间复杂度为O(cn)。

根据2节的性质及算法MVC(G,S)，可以得出以下结论，图G=(V,E)中任意顶点vi的度d(vi)≤3的情况下,显然可以在多项式时间内求解。由此我们可知此算法MVC(G,S)的时间复杂度可以根据T(n)=T(n-1)+T(n-5) ，由此可知用传统方法求解T(n)，即求方程x5=x4+1在1与2之间的最大解，得x≈1.3250，因此得T(n)=1.325n，由此可以得出采用传统方法得到的时间复杂度为O(1.325n)。

其中T(n-1)代表选中的顶点v包含在S中后的子问题，该子问题的规模减少1；T(n-5)代表选中的顶点v不包含在S中，因为我们从度最大的顶点进行分支降阶，所以顶点v的度d(v)≥4，因此此时的子问题的规模共减少5。

2.3加权分治技术分析下的时间复杂性

为了提高2.1节中算法MVC(G,S)的时间复杂性，下面应用加权分治技术对本文中算法MVC(G,S)的时间复杂性进行具体分析。加权分治技术的核心思想在于根据问题特征设置一组相应的权值，显然在MVC问题中,可以根据顶点的度来赋予不同的权值。显然在最小顶点覆盖问题中度数越大的顶点所赋予的权值应该越大。因此我们可以根据顶点的度设置一组相应的权值，具体如下：

(1)度数为0、1和2的顶点，设置权值为：h0=h1=h2=0；

(2)度数为3的顶点，设置权值为：h3=0.6；

(3)度数为4的顶点，设置权值为：h4=0.9；

(4)度数为大于等于5的顶点，设置权值为h≥5=1。

该方法把图中所有顶点的权值之和作为问题的规模，设图中度为i的顶点数量和权值分别为ki和hi，显然可以得出问题的规模h=0.6×n3+0.9×n4+n≥5

①图G(V,E)中度最大等于4，取一度为4的顶点v，设v1,v2,v3,v4分别表示v的四个邻接顶点，其中d(v1),d(v2),d(v3),d(v4)分别表示这四个邻接顶点的度，同时ni则表示这四个邻接顶点中度为i的个数，由此可以根据公式2求解此情况下的时间复杂度。

T(h)=T[h-0.9-(0.9-0.6)n4-(0.6-0)n3]+T(h-0.9-h4n4-h3n3)

(1)

其中公式(1)中h-0.9-(0.9-0.6)n4-(0.6-0)n3表示：由于将顶点v加入最小顶点覆盖集S中引起的问题规模发生的变化。公式(1)中h-0.9-h4n4-h3n3表示：由于顶点v不在最小顶点覆盖集S中所引起的问题规模发生的变化。

由此我们可以根据公式(1)得出当顶点v最大度为4的时候的所有情况的递推式，计算过程及结果如表1。

表1　度为4顶点进行分支的递推式

根据表1可以得出max(c)=1.246，由此可知在最大度为4的情况下算法MVC(G,S)的时间复杂度为O(1.246h)

② 图G(V,E)中最大度等于5的顶点，设该顶点为v，v1,v2,v3,v4,v5分别表示顶点v的五个邻接顶点。其中d(v1),d(v2),d(v3),d(v4),d(v5)分别表示这五个邻接顶点的度，同时ni则表示这五个邻接顶点中度为i的个数。

因此，以图中所有顶点的权值之和h作为问题的规模，可以得出如下递归公式：

T(h)=T[h-1-(1-0.9)n5-(0.9-0.6)n4-(0.6-0)n3]+T(h-1-n≥5-h4n4-h3n3)

(2)

其中公式(2)中h-1-(1-0.9)n5-(0.9-0.6)n4-(0.6-0)n3表示：由于将顶点v加入最小顶点覆盖集S中引起的问题规模发生的变化。公式(2)中h-1-n≥5-h4n4-h3n3表示：由于顶点v不在最小顶点覆盖集S中所引起的问题规模发生的变化。

由此我们可以根据公式(2)得出当顶点v最大度为5的时候的所有情况的递推式，计算过程及结果如表2：

表2　度为5顶点进行分支的递推式

根据表2可以得出max(c)=1.239。由此可知在最大度为5的情况下时间复杂度为O(1.239h)，并且该复杂性小于等于O(1.239h)。

③如果存在d(v)大于等于6的顶点，最坏情况下的时间复杂度递归式为T(h)=T(h-1)+T(h-7)，根据计算可以得出其时间复杂度为O(1.255h)。

综合上述分述可知算法MVC(G,S)的时间复杂度必定小于或等于O(1.255h)，同时由于h≤n,所以算法MVC(G,S)最坏情况下的时间复杂度为O(1.255n)。

3结论

本文依据最小顶点覆盖问题的基本性质设计出一个基于分支降阶的递归算法用于求解MVC问题，同时在不改变算法本身的情况下，运用常规和加权分治两种方法分析了该算法的复杂度。通过分析表明加权分治技术更适合用于分析此类算法的复杂度，所得出的算法时间复杂度相对常规分析更精确。在接下来的研究中，应该将加权分治技术应用到各种递归算法的时间复杂度分析中，尤其是各类NP完全问题以及部分NP-Hard问题都存在这类递归算法。同时为了进一步降低此类问题的时间复杂度，应当设计更加合理的权值，充分利用权值的变化来分析和降低算法的时间复杂度。

参考文献：

[1]Marco Cesati. Compendium of parameterized problems[M]. 2006.

[2]Balasubramanian R, Fellows M R, Raman V. An improved fixed parameter algorithm for vertex cover [J]. Information Processing Letters, 1998, 65(3): 163-168.

[3]J Chen, I Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms[J]. Journal of Computer and System Sciences, 2003, 67(4): 833-847.

[4]Chen J, Kanj I, Jia W. Vertex cover: further observation and further improvements[J]. Journal of Algorithms, 2001, 41(2): 280-301.

[5]Niedermeier R, Rossmanith P. On efficient fixed parameter algorithms for weighted vertex cover[J]. Journal of Algorithms, 2003, 47(2): 63-77.

[6]Stege U, Fellows M R. An improved fixed-parameter-tractable algorithm for vertex cover[R]. Technical Report 318, Department of Computer Science, ETH Zurich Apr. 1999.

[7]Fomin F V, Grandoni, Kratsch D. Measure and conquer: a simple O(20.288n) independent set algorithm[C]. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, 2006, 18-25.

[8]Garey M, Johnson D. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco: W.H. Freeman and company, 1979.

[9]Fomin F V, Grandoni F, Kratsch D. Measure and conquer: domination a case study[C]. Proceedings of the 32nd International Colloquium on Automata, Languages and Programming , 2005, 191-203.

[10]马振宇.加权分治技术在Set Packing问题中的应用与研究[D].硕士学位论文,中南大学,2007.

[11]石磊. 使用度量与分治方法分析和设计精确算法[D].硕士学位论文,上海交通大学,2010.

[12]Alber J, Fan H, Fellows M R, et al. A refined search tree technique for dominating set on planar graphs[J]. Journal of Computer and Sciences, 2005, 71(4): 385-405.

[13]Saket Saurabh. Exact algorithms for optimization and parameterized versions of some graph theoretic problems[D]. Homi Bhabha National Institute, 2008.

[14]Ning Ai-bing, Ma Liang, Xiong Xiao-hua. Fast reduction algorithm for minimum vertex cover problem[J]. Journal of Chinese Computer Systems. 2008. 29(4): 1282-1285.