基于搜索樹的平面圖支配集算法

1、基于搜索樹的平面圖支配集算法*    摘要:許多來自工業(yè)應(yīng)用的優(yōu)化問題都是NP難問題。確定參數(shù)可解FPT作為處理這類問題的另外一種思路,在最近的10多年中受到了廣泛的關(guān)注。支配集問題是圖論中最重要的NP完全的組合優(yōu)化問題之一,即使對(duì)于FPT體系而言,一般圖中的支配集問題屬于W2完全的,意味著不可能設(shè)計(jì)出復(fù)雜度為f(k)no(1)的算法。在本文中,我們考慮在給定的平面圖G= (V ,E)中參數(shù)化支配集問題,給定參數(shù)k,看是否存在大小為k的頂點(diǎn)集合支配圖中的其他頂點(diǎn),當(dāng)把問題限定在平面圖上,這個(gè)問題屬于確定參數(shù)可解。本文給出了基于兩組歸約規(guī)則的搜索樹算法,通

2、過使用規(guī)約技術(shù)化簡實(shí)例,構(gòu)造搜索樹,得到了復(fù)雜度為O(8kn)的算法,同時(shí)通過相關(guān)實(shí)驗(yàn)結(jié)果顯示了歸約規(guī)則對(duì)算法的作用。關(guān)鍵詞:算法;搜索樹;支配集;確定參數(shù)可解1引言許多來自工業(yè)應(yīng)用的優(yōu)化問題都是NP難問題。根據(jù)NP完全性理論,這些問題很難有多項(xiàng)式時(shí)間算法,除非P=NP,正是由于這類問題本身的難解性,人們很長一段時(shí)間都是通過設(shè)計(jì)多項(xiàng)式時(shí)間的近似算法去解決此類問題,更多背景知識(shí)可參考文獻(xiàn)1。確定參數(shù)可解(Fixed-Parameter Tractability,簡稱FPT)作為處理這類問題的另外一種思路,在最近的10多年中受到了廣泛的關(guān)注,它的起源可以追溯到Graph Minor Theorem

3、定理1。很多NP難問題在給定參數(shù)的情況下是可解的(如文獻(xiàn)2),這類給定參數(shù)可解的問題現(xiàn)在都被歸于FPT1,更多的關(guān)于使用參數(shù)處理問題的思路見文獻(xiàn)3。支配集問題是圖論中最重要的組合優(yōu)化問題之一。在FPT的體系下,對(duì)一般的圖而言支配集問題屬于W2-Complete,意味著參數(shù)難解,即不可能設(shè)計(jì)出一個(gè)f(k)no(1)復(fù)雜度的算法(其中f(k)是任意只依賴k的可計(jì)算函數(shù))。即使將此問題限定在平面圖的范圍中依然屬于NP-Complete。本文中,我們考慮在給定的無向平面圖G(V, E)中參數(shù)化支配集問題,即給出參數(shù)k,看是否存在一個(gè)大小為k的頂點(diǎn)集合可以支配圖中的其他頂點(diǎn),這個(gè)問題屬于確定參數(shù)可解(F

4、ixed-ParameterTractable)。本文給出基于兩組歸約規(guī)則的搜索樹算法以及相關(guān)實(shí)驗(yàn)。2基本定義和問題描述給定無向平面圖G(V, E),V為頂點(diǎn)集合,E為邊集合;取頂點(diǎn)uV,則N(u)表示所有與u鄰接的點(diǎn),即N(u)=v|(u ,v )E;支配集即取頂點(diǎn)集合V的一個(gè)子集V,對(duì)圖G中的任意剩余頂點(diǎn)v,都存在某一頂點(diǎn)uV,使得邊u, v連接頂點(diǎn)v。所謂平面圖即將圖嵌入到一個(gè)平面中,不存在相交的邊?；趨?shù)k的k-支配集問題中,我們?cè)O(shè)計(jì)了一個(gè)基于搜索樹的算法,將頂點(diǎn)劃分成為白色頂點(diǎn)集合W和黑色定點(diǎn)集合B,V=B+W(+表示無公共頂點(diǎn)的并運(yùn)算)。問題的形式化描述如下:輸入:一個(gè)黑白圖G=

5、(B+W,E)和一個(gè)正整數(shù)k。參數(shù):k。問題:是否存在至多k個(gè)頂點(diǎn)的集合V V,滿足對(duì)任意頂點(diǎn)uB,存在頂點(diǎn)uNuV或者說是否存在大小為k的頂點(diǎn)集合可以支配所有的黑色頂點(diǎn)。在構(gòu)建搜索樹的過程中,我們將根據(jù)度數(shù)較小的黑色頂點(diǎn)對(duì)搜索樹分支擴(kuò)展。通過對(duì)圖G的限定,可以保證應(yīng)用歸約后的圖中必然存在頂點(diǎn)u,滿足deg(u)d。由于沒有限定所有頂點(diǎn)度數(shù)都小于d,選入支配集的頂點(diǎn)不一定是黑色的。這個(gè)形式化的描述直接產(chǎn)生了O(d+1)kn)基于搜索樹的支配集算法。3歸約規(guī)則和搜索樹算法在這里使用兩組歸約法則,從不同的視角對(duì)支配集進(jìn)行處理。兩組歸約基于同樣的原則:通過對(duì)圖的結(jié)構(gòu)的探索,試圖用更簡單但不影響問題解

6、答的結(jié)構(gòu)來進(jìn)行替換。如果對(duì)原問題的每個(gè)實(shí)例(G, k)應(yīng)用歸約后得到實(shí)例(G, k),(G, k)存在解當(dāng)且僅當(dāng)(G,k)存在解,我們稱一組歸約規(guī)則對(duì)某問題sound。第一組歸約中,對(duì)頂點(diǎn)v的鄰接點(diǎn)進(jìn)行處理。依據(jù)節(jié)點(diǎn)所具有的不同的鄰居結(jié)構(gòu)4,將v的鄰居節(jié)點(diǎn)分為三個(gè)集合N1(v)、N2(v)和N3(v)。如圖1a所示。N1(v) :=uN(v) : N(u)N(v)N2(v) :=uN(v)N1(v) : N(u)N1(v)N3(v) :=N(v)(N1(v)N2(v)通過三個(gè)子集的定義,可知N1(v)中的頂點(diǎn)不能被N3中的頂點(diǎn)支配。因此,為了控制N3(v)中的頂點(diǎn),一個(gè)好的選擇是將頂點(diǎn)v加入支

7、配集。根據(jù)歸約規(guī)則1,這確實(shí)是最優(yōu)選擇。規(guī)則1對(duì)頂點(diǎn)v而言,如果N3(v)不空,那么,從圖中移除N2(v)和N3(v)中的頂點(diǎn),在圖G中添加新頂點(diǎn)v以及邊v, v。如圖1b所示。通過新加入v頂點(diǎn)作為“gadget vertex”,使得在歸約后的圖中需選擇v或者v作為支配集的最優(yōu)選擇4。第二組歸約則對(duì)某些結(jié)構(gòu)進(jìn)行簡化。在構(gòu)造搜索樹的過程中,將始終從歸約過的實(shí)例branch-ing。因此,將不斷地使用歸約對(duì)圖進(jìn)行處理。當(dāng)一個(gè)頂點(diǎn)u通過應(yīng)用某條歸約被置入支配集D中,目標(biāo)參數(shù)k減小為k-1且將u的所有鄰居置為白色5。圖1使用規(guī)約法則對(duì)支配集v進(jìn)行處理的結(jié)果歸約規(guī)則如下:(1)刪除白色頂點(diǎn)之間的邊。(2

8、)刪除度為1的白色頂點(diǎn)。(3)如果存在度為1的黑色頂點(diǎn)w,它的鄰居為u,則刪除w,將u置入支配集,同時(shí)將k置為k-1。(4)如果存在度為2的白色頂點(diǎn)u,它有兩個(gè)黑色鄰居為u1和u2由邊u1, u2連接,則刪除頂點(diǎn)u。(5)如果存在度為2的白色頂點(diǎn)u,它有兩個(gè)黑色鄰居u1和u3,且存在黑色頂點(diǎn)u2使得邊u1,u2和 u2, u3存在,則刪除頂點(diǎn)u。(6)如果存在度為2的白色頂點(diǎn)u,它有兩個(gè)黑色鄰居u1和u3,且存在白色頂點(diǎn)u2使得邊u1,u2和 u2, u3存在,則刪除頂點(diǎn)u。(7)如果存在度為3的白色頂點(diǎn)u,它有三個(gè)黑色鄰居u1、u2和u3,且在圖中存在邊u1, u2和 u2, u3,則刪除頂

9、點(diǎn)u。引理1如果G=(B+W,E)是一個(gè)平面圖,且已經(jīng)不能再應(yīng)用第二組歸約規(guī)則,那么必然存在一個(gè)黑色頂點(diǎn)uB,滿足degG(u)7。引理的證明可以參考文獻(xiàn)5,主要使用歐拉公式進(jìn)行了十分復(fù)雜的推導(dǎo)。引理保證了應(yīng)用歸約后的圖中必然存在某個(gè)度為7的頂點(diǎn),從而保證搜索樹算法的復(fù)雜度為O(7+1)kn)。算法描述如下:pds-st(B, W, E, k, S):/B是圖中黑色頂點(diǎn)的集合/W是圖中白色頂點(diǎn)的集合/E是圖中邊的集合/k是實(shí)例的參數(shù)/S是當(dāng)前找到的部分解/預(yù)處理對(duì)(B, W, k)應(yīng)用歸約規(guī)則到無法應(yīng)用為止;IFk=0 andB=W=then returnS;IFk=0 and (BorW=)

10、 then return;/branching ifk>0選擇最小度數(shù)的黑色頂點(diǎn)v;B:=BNv;W:=WNv;For eachvBDOE:=u, v|uBW;S:=pds-st(BNv, (WNv,EE, k-1,Sv);IFsTHEN break;OD;IFS=THENFor eachvWDOE:=u, v|uBW;S:=pds-st(BNv, (WNvv, EE, k-1, Sv;IFsTHEN break;OD;ReturnS;4實(shí)驗(yàn)4.1實(shí)現(xiàn)及測(cè)試用例算法使用C+實(shí)現(xiàn),使用了LEDA6作為主要的包來進(jìn)行開發(fā)。應(yīng)用兩組歸約規(guī)則降低圖的復(fù)雜度,從而保證構(gòu)造出有效的搜索樹。實(shí)驗(yàn)硬件平

11、臺(tái)使用Pentium4 3.2GHz處理器,2G內(nèi)存。LEDA構(gòu)建了組合問題和幾何計(jì)算的良好的軟件平臺(tái),提供了相當(dāng)多的數(shù)據(jù)類型和算法。它包括了大部分?jǐn)?shù)據(jù)類型和算法,如堆棧、隊(duì)列、鏈表、集合、字典、有序序列、劃分、優(yōu)先級(jí)隊(duì)列等,以及各種圖、點(diǎn)、線段、平面、多邊形,以及圖論、網(wǎng)絡(luò)和計(jì)算幾何中的多個(gè)算法。LEDA能支持很多領(lǐng)域的應(yīng)用6。實(shí)驗(yàn)測(cè)試用例基于純組合方法,使用LEDA包中的庫函數(shù)void random_planar_graph(graph&G, intn,intm)產(chǎn)生。4.2實(shí)驗(yàn)結(jié)果表1是在不同節(jié)點(diǎn)數(shù)和不同邊密度的圖應(yīng)用兩組歸約規(guī)則后算法得到的結(jié)果。可以看出,隨著圖大小的變化,歸約

12、規(guī)則的作用變化很大,同時(shí)能清楚地觀察到在稀疏圖中,歸約規(guī)則的結(jié)果更好。將降低算法的效率,因歸約所需的額外開銷所占比例較大;隨著圖中邊數(shù)和頂點(diǎn)數(shù)的增大,應(yīng)用兩組歸約的算法運(yùn)行時(shí)間明顯超過后者。5結(jié)束語支配集在電子線路設(shè)計(jì)、計(jì)算機(jī)網(wǎng)絡(luò)以及無線傳感器網(wǎng)絡(luò)等領(lǐng)域存在廣泛的應(yīng)用。本文在FPT體系下應(yīng)用歸約技術(shù)得到了此問題的解,對(duì)歸約規(guī)則的作用以及算法運(yùn)行時(shí)間作了比較,展示了基于FPT的算法強(qiáng)大力量。參考文獻(xiàn):1Fellows M R , Langston M A . Nonconstructive Tools forProving Polynomial-Time DecidabilityJ. Journ

13、al of theACM , 1988, 35(3):727-739.2Fellows M R, Langston M A. On Search, Decision and theEfficiency of Polynomial-Time Algorithms J. Journal ofComputer and Systems Sciences, 1994,49(3):769-779.3GDowney R, Fellows M R. Parameterized ComplexityM.Berlin:Springer-Verlag, 1999.4Alber J, Fellows M R, Niedermeier R. Polynomial-Time Da-ta Reduction for Dominating SetJ. Journal of the ACM,2004,51(3):363-384.5Alber J, Fan H, Fellows M R, et al. A Refined Search TreeTechnique for Dominatin