最小頂點(diǎn)覆蓋問題的加權(quán)分治算法

最小頂點(diǎn)覆蓋問題的加權(quán)分治算法

陳吉珍，寧愛兵，支志兵，王永斐，張惠珍

(上海理工大學(xué)管理學(xué)院，上海200093)

摘要：最小頂點(diǎn)覆蓋問題是組合優(yōu)化中經(jīng)典NP-Hard問題之一，其在實(shí)際問題中有著廣泛的應(yīng)用。加權(quán)分治技術(shù)是算法設(shè)計(jì)和復(fù)雜性分析中的新技術(shù)，該技術(shù)主要用于對分支降階的遞歸算法進(jìn)行復(fù)雜性分析，其核心思想可以理解為依據(jù)問題不同的特征設(shè)置一組相應(yīng)的權(quán)值，以求降低該算法最壞情況下的時間復(fù)雜度。本文依據(jù)加權(quán)分治技術(shù)設(shè)計(jì)出一個分支降階遞歸算法來求解最小頂點(diǎn)覆蓋問題，并通過加權(quán)分治技術(shù)分析得出該算法的時間復(fù)雜度為O(1.255n)，優(yōu)于常規(guī)分析下的時間復(fù)雜度O(1.325n) 。本文中的結(jié)果表明運(yùn)用上述方法降低算法的時間復(fù)雜度是非常有效的。

關(guān)鍵詞：圖論；算法復(fù)雜性；加權(quán)分治技術(shù)； 分支降階技術(shù)； 最小頂點(diǎn)覆蓋

收稿日期：2014-11-04

基金項(xiàng)目：國家自然科學(xué)基金(71401106);上海市一流學(xué)科建設(shè)項(xiàng)目資助(S1201YLXK); 高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金聯(lián)合資助課題(20123120120005)

作者簡介：陳吉珍(1990-)，女，碩士生，研究方向?yàn)樗惴ā⑽锪鞴こ蹋粚帎郾?1972-)，男，博士，副教授，研究方向?yàn)樗惴ㄔO(shè)計(jì)、系統(tǒng)工程；支志兵(1990-)，男，碩士生，研究方向?yàn)樗惴ā⑾到y(tǒng)工程；王永斐(1988-)，男，碩士生，研究方向?yàn)樗惴ā⑾到y(tǒng)工程；張惠珍(1979-)，女，博士，副教授，研究方向?yàn)閮?yōu)化算法。

中圖分類號：O223文章標(biāo)識碼：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引言

頂點(diǎn)覆蓋問題[1]及其各種變形問題在圖論、組合數(shù)學(xué)、運(yùn)籌學(xué)、管理及計(jì)算機(jī)科學(xué)等領(lǐng)域被廣泛的研究。最小頂點(diǎn)覆蓋(minimum vertex cover , 以下簡稱MVC)問題是頂點(diǎn)覆蓋問題中最常見、研究最多及應(yīng)用最廣的一種，也是組合優(yōu)化中典型NP-Hard問題，除非P=NP,否則不存在多項(xiàng)式時間算法。人們對MVC問題的精確算法、近似算法和啟發(fā)示算法做了大量研究[2～6]。近年來，由于加權(quán)分治分析技術(shù)[7～11]的提出，基于加權(quán)分治技術(shù)的精確算法[12,13]的設(shè)計(jì)和分析被廣泛應(yīng)用于求解NP-Hard問題中，以期求得精確解的同時，獲得更好更逼近的時間上界；其核心思想可以理解為根據(jù)問題不同特征設(shè)置一組相應(yīng)的權(quán)值，其目標(biāo)就是盡可能提高算法的效率及降低算法的時間復(fù)雜度。

本文第1節(jié)給出了MVC問題的定義及其性質(zhì)和證明；第2節(jié)根據(jù)定義和性質(zhì)設(shè)計(jì)出基于分支降階的遞歸算法，并對算法進(jìn)行常規(guī)分析得出時間復(fù)雜度為O(1.325n)，同時運(yùn)用加權(quán)分治技術(shù)進(jìn)行復(fù)雜度分析，得出其時間復(fù)雜度為O(1.255n)；最后對本文研究內(nèi)容加以總結(jié)并提出進(jìn)一步的研究方向。

1最小頂點(diǎn)覆蓋問題的定義及性質(zhì)

設(shè)任意給定簡單無向圖G=(V,E)，其中V表示頂點(diǎn)集，E表示邊集；S表示MVC的頂點(diǎn)集；|S|表示集合S的個數(shù)；d表示任意頂點(diǎn)v的度；N(v)={h|(v,h)∈E}表示頂點(diǎn)v的一階開領(lǐng)域；N[v]=N(v)∪v表示頂點(diǎn)v的一階閉鄰域；N2(v)表示頂點(diǎn)v的二階領(lǐng)域，即N(v)的鄰接頂點(diǎn)，且不包括v本身。

定義：最小頂點(diǎn)覆蓋，即任意給定的無向圖G=(V,E)，求解一個最少頂點(diǎn)個數(shù)集合S使得任意邊e=(u,v)∈E,有u∈S或v∈S,也就是S中的頂點(diǎn)覆蓋了邊集E。

性質(zhì)1：任取一條屬于G圖中的邊E=(vi,vj)，并定義M={vi,vj};則對于最小頂點(diǎn)覆蓋的頂點(diǎn)集S都滿足M∩S≠?。

證明：根據(jù)最小頂點(diǎn)覆蓋集定義顯然成立。

性質(zhì)2：圖中任意頂點(diǎn)vi,如果d(vi)=0，那么vi必定不包含在S中。

證明：因?yàn)槎葹榈?頂點(diǎn)都是一個孤立點(diǎn)，不加入S顯然不會影響到其它頂點(diǎn)且滿足頂點(diǎn)覆蓋的要求。

性質(zhì)3：若圖G中任意頂點(diǎn)vi的度d(vi)=1，則該圖必然是n條孤立的直線，直線兩端為其頂點(diǎn)，則任意一條直線必須只取一個頂點(diǎn)加入S中，顯然問題可以在多項(xiàng)式時間內(nèi)解決。

證明：顯然成立，否則與所求問題相矛盾。

性質(zhì)4：若圖G中任意頂點(diǎn)vi的度d(vi)≤ 2，則該問題多項(xiàng)式時間內(nèi)可求解。

證明：由性質(zhì)2可以去掉所有度為0的頂點(diǎn)，之后只有以下2種情況：

(1)圖中既有度為1也有度為2的頂點(diǎn)，則任取一個d(vi)=1的頂點(diǎn)vi,直接刪除，并將N(vi)加入S，直到圖中不存在度為1的頂點(diǎn)，此時顯然可以在多項(xiàng)式時間內(nèi)求解。

(2)圖中的所有頂點(diǎn)度都為2，此時實(shí)際上是一條或多條簡單回路，此時顯然也可以在多項(xiàng)式時間內(nèi)求解。

性質(zhì)5[14]：若圖G中頂點(diǎn)vi的度d(vi)=2，如果其鄰接頂點(diǎn)w1與w2之間不相連，則刪除圖中的頂點(diǎn)v,w1,w2并由一個新頂點(diǎn)v*代替，同時把原來聯(lián)結(jié)到w1和w2的所有邊聯(lián)結(jié)到新增點(diǎn)v*上。新加入的點(diǎn)v*在取得V*后按下面的規(guī)則處理。

(1) 若最終的S中包含點(diǎn)v*, 則S=S-{v*} + {w1,w2};

(2) 若最終的S中不包含點(diǎn)v*, 則S=S-{v*} +{v}。

證明：(1)如果最終的S中包含v*，那么證明邊E(v*)中有一些邊必須要v*來覆蓋，故此w1,w2至少有一個在S中，同時為了覆蓋邊(v,w1)和邊(v,w2)則應(yīng)該另加入一個頂點(diǎn)，因此應(yīng)該加入w1,w2最佳。(2)若最終的S中不包含v*，那么證明邊E(v*)中已被其它頂點(diǎn)覆蓋，此時只需將v加入S中即可。

性質(zhì)6：若圖G中存在N[v]?N[u],則直接將頂點(diǎn)v排除出S并將頂點(diǎn)u加入S中，同時稱頂點(diǎn)v被頂點(diǎn)u所支配。

證明：顯然由于頂點(diǎn)u能夠支配頂點(diǎn)v所支配的所有邊，因此將頂點(diǎn)u加入S的效果要比將頂點(diǎn)v加入S的效果更好。

2最小頂點(diǎn)覆蓋問題的算法及復(fù)雜性分析

2.1最小頂點(diǎn)覆蓋問題的算法

根據(jù)本文第2節(jié)的定義及性質(zhì)，我們可以將度為0，1，2的頂點(diǎn)進(jìn)行約簡處理，由此我們可以設(shè)計(jì)出MVC問題基于分支降階的遞歸算法，用自然語言描述算法如下。

算法: MVC(G,S)

輸入:圖G=(V,E)

輸出：一個最小頂點(diǎn)覆蓋集S，記為min(S)。

Step 1初始化：輸入一個G,此時S=?;

Step 2找出圖G中度為0的頂點(diǎn)集合V0，根據(jù)性質(zhì)1，直接令V=V-V0，即從圖G中刪除頂點(diǎn)集合V0;

Step 3如果圖G中存在頂點(diǎn)v∈V,且d(v)=1,N(v)=u,根據(jù)性質(zhì)4，直接令V=V-v-u，S=S∪u，即從圖G中刪除頂點(diǎn)v,u，同時刪掉v,u所關(guān)聯(lián)的邊，并將u加入S中；

Step 4存在頂點(diǎn)v∈V,且d(v)=2,N(v)={w1,w2},則可分為以下兩種情況討論：

Step 4.1如果{w1,w2}∈E，此時v被點(diǎn)w1和點(diǎn)w2所支配；根據(jù)性質(zhì)5可知；此時直接令V=V-v-w1-w2，S=S∪w1∪w2，即從圖G中刪除頂點(diǎn)u,w1,w2，同時刪掉u,w1,w2所關(guān)聯(lián)的邊，并將w1,w2加入S中；

Step 4.2如果{w1,w2}?E，此時根據(jù)性質(zhì)5此時直接返回G(V*，S)

Step 5如果存在頂點(diǎn)v∈V,且d(v)≥3，則分以下兩種情況：

Step 5.1如果G圖中所有頂點(diǎn)vi都等于3，則任意選取一個頂點(diǎn)進(jìn)行一次分支后，可直接返回Step2即可。

Step 5.2選取G(V,E)中度最大的頂點(diǎn)v∈V,顯然d(v)≥4,返回:MVC{G(V-v),S∪w;G(V-N[v]),S∪N(v)]}

Step 6輸出min (S),算法結(jié)束。

2.2傳統(tǒng)分析方法的時間復(fù)雜性

下面我們依據(jù)傳統(tǒng)技術(shù)對上述算法的時間復(fù)雜性進(jìn)行分析,根據(jù)2.1節(jié)中算法MVC(G,S)可知當(dāng)圖中度小于等于2可以直接約簡，在多項(xiàng)式時間內(nèi)求出；同時當(dāng)最大度為3時也可以在多項(xiàng)式時間內(nèi)求出，所以此處所求的圖的任一頂點(diǎn)的度都大于等于3,且最大度大于3。因此令頂點(diǎn)個數(shù)n為問題的規(guī)模，T(n)為搜索樹產(chǎn)生的葉子頂點(diǎn)個數(shù)，由此我們可以得出遞推通項(xiàng)式：T(n)=T(n-1)+T(n-d-1)。

設(shè)T(n)=cn，其中c為待求解的常數(shù)，則cn=cn-1+cn-k由此我們可以得出ck=ck-1+1，其中k=d(vi)+1就可求得c，并得出其時間復(fù)雜度為O(cn)。

根據(jù)2節(jié)的性質(zhì)及算法MVC(G,S)，可以得出以下結(jié)論，圖G=(V,E)中任意頂點(diǎn)vi的度d(vi)≤3的情況下,顯然可以在多項(xiàng)式時間內(nèi)求解。由此我們可知此算法MVC(G,S)的時間復(fù)雜度可以根據(jù)T(n)=T(n-1)+T(n-5) ，由此可知用傳統(tǒng)方法求解T(n)，即求方程x5=x4+1在1與2之間的最大解，得x≈1.3250，因此得T(n)=1.325n，由此可以得出采用傳統(tǒng)方法得到的時間復(fù)雜度為O(1.325n)。

其中T(n-1)代表選中的頂點(diǎn)v包含在S中后的子問題，該子問題的規(guī)模減少1；T(n-5)代表選中的頂點(diǎn)v不包含在S中，因?yàn)槲覀儚亩茸畲蟮捻旤c(diǎn)進(jìn)行分支降階，所以頂點(diǎn)v的度d(v)≥4，因此此時的子問題的規(guī)模共減少5。

2.3加權(quán)分治技術(shù)分析下的時間復(fù)雜性

為了提高2.1節(jié)中算法MVC(G,S)的時間復(fù)雜性，下面應(yīng)用加權(quán)分治技術(shù)對本文中算法MVC(G,S)的時間復(fù)雜性進(jìn)行具體分析。加權(quán)分治技術(shù)的核心思想在于根據(jù)問題特征設(shè)置一組相應(yīng)的權(quán)值，顯然在MVC問題中,可以根據(jù)頂點(diǎn)的度來賦予不同的權(quán)值。顯然在最小頂點(diǎn)覆蓋問題中度數(shù)越大的頂點(diǎn)所賦予的權(quán)值應(yīng)該越大。因此我們可以根據(jù)頂點(diǎn)的度設(shè)置一組相應(yīng)的權(quán)值，具體如下：

(1)度數(shù)為0、1和2的頂點(diǎn)，設(shè)置權(quán)值為：h0=h1=h2=0；

(2)度數(shù)為3的頂點(diǎn)，設(shè)置權(quán)值為：h3=0.6；

(3)度數(shù)為4的頂點(diǎn)，設(shè)置權(quán)值為：h4=0.9；

(4)度數(shù)為大于等于5的頂點(diǎn)，設(shè)置權(quán)值為h≥5=1。

該方法把圖中所有頂點(diǎn)的權(quán)值之和作為問題的規(guī)模，設(shè)圖中度為i的頂點(diǎn)數(shù)量和權(quán)值分別為ki和hi，顯然可以得出問題的規(guī)模h=0.6×n3+0.9×n4+n≥5

①圖G(V,E)中度最大等于4，取一度為4的頂點(diǎn)v，設(shè)v1,v2,v3,v4分別表示v的四個鄰接頂點(diǎn)，其中d(v1),d(v2),d(v3),d(v4)分別表示這四個鄰接頂點(diǎn)的度，同時ni則表示這四個鄰接頂點(diǎn)中度為i的個數(shù)，由此可以根據(jù)公式2求解此情況下的時間復(fù)雜度。

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表示：由于將頂點(diǎn)v加入最小頂點(diǎn)覆蓋集S中引起的問題規(guī)模發(fā)生的變化。公式(1)中h-0.9-h4n4-h3n3表示：由于頂點(diǎn)v不在最小頂點(diǎn)覆蓋集S中所引起的問題規(guī)模發(fā)生的變化。

由此我們可以根據(jù)公式(1)得出當(dāng)頂點(diǎn)v最大度為4的時候的所有情況的遞推式，計(jì)算過程及結(jié)果如表1。

表1　度為4頂點(diǎn)進(jìn)行分支的遞推式

根據(jù)表1可以得出max(c)=1.246，由此可知在最大度為4的情況下算法MVC(G,S)的時間復(fù)雜度為O(1.246h)

② 圖G(V,E)中最大度等于5的頂點(diǎn)，設(shè)該頂點(diǎn)為v，v1,v2,v3,v4,v5分別表示頂點(diǎn)v的五個鄰接頂點(diǎn)。其中d(v1),d(v2),d(v3),d(v4),d(v5)分別表示這五個鄰接頂點(diǎn)的度，同時ni則表示這五個鄰接頂點(diǎn)中度為i的個數(shù)。

因此，以圖中所有頂點(diǎn)的權(quán)值之和h作為問題的規(guī)模，可以得出如下遞歸公式：

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表示：由于將頂點(diǎn)v加入最小頂點(diǎn)覆蓋集S中引起的問題規(guī)模發(fā)生的變化。公式(2)中h-1-n≥5-h4n4-h3n3表示：由于頂點(diǎn)v不在最小頂點(diǎn)覆蓋集S中所引起的問題規(guī)模發(fā)生的變化。

由此我們可以根據(jù)公式(2)得出當(dāng)頂點(diǎn)v最大度為5的時候的所有情況的遞推式，計(jì)算過程及結(jié)果如表2：

表2　度為5頂點(diǎn)進(jìn)行分支的遞推式

根據(jù)表2可以得出max(c)=1.239。由此可知在最大度為5的情況下時間復(fù)雜度為O(1.239h)，并且該復(fù)雜性小于等于O(1.239h)。

③如果存在d(v)大于等于6的頂點(diǎn)，最壞情況下的時間復(fù)雜度遞歸式為T(h)=T(h-1)+T(h-7)，根據(jù)計(jì)算可以得出其時間復(fù)雜度為O(1.255h)。

綜合上述分述可知算法MVC(G,S)的時間復(fù)雜度必定小于或等于O(1.255h)，同時由于h≤n,所以算法MVC(G,S)最壞情況下的時間復(fù)雜度為O(1.255n)。

3結(jié)論

本文依據(jù)最小頂點(diǎn)覆蓋問題的基本性質(zhì)設(shè)計(jì)出一個基于分支降階的遞歸算法用于求解MVC問題，同時在不改變算法本身的情況下，運(yùn)用常規(guī)和加權(quán)分治兩種方法分析了該算法的復(fù)雜度。通過分析表明加權(quán)分治技術(shù)更適合用于分析此類算法的復(fù)雜度，所得出的算法時間復(fù)雜度相對常規(guī)分析更精確。在接下來的研究中，應(yīng)該將加權(quán)分治技術(shù)應(yīng)用到各種遞歸算法的時間復(fù)雜度分析中，尤其是各類NP完全問題以及部分NP-Hard問題都存在這類遞歸算法。同時為了進(jìn)一步降低此類問題的時間復(fù)雜度，應(yīng)當(dāng)設(shè)計(jì)更加合理的權(quán)值，充分利用權(quán)值的變化來分析和降低算法的時間復(fù)雜度。

參考文獻(xiàn)：

[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]馬振宇.加權(quán)分治技術(shù)在Set Packing問題中的應(yīng)用與研究[D].碩士學(xué)位論文,中南大學(xué),2007.

[11]石磊. 使用度量與分治方法分析和設(shè)計(jì)精確算法[D].碩士學(xué)位論文,上海交通大學(xué),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.