樹上具有懲罰費用的限制性node multicut問題的近似算法

楊惠娟,段江梅,楊子蘭

(1.昭通學院數學與統計學院,云南 昭通 657000; 2.麗江文化旅游學校信息學院,云南 麗江 674199)

0 引言

multicut問題是圖論與組合優化中非常著名的問題,它具有邊和點兩種形式,點形式的multicut問題是指:給定賦權圖G=(V,E;w)及一個終端點對集合H?V×V,其中w:V→R+,求G的一個頂點子集D,使得H中的所有頂點對在G-D中不連通,目標是使得D的權重盡可能小.

限制性node multicut問題是點形式multicut問題的一類子問題,該問題要求所求的頂點子集中不允許有終端點.GUO等[1]研究了完全圖、分裂圖、區間圖上的點multicut 問題,并證明了該問題限制在這三類特殊圖上時也是NP難問題.PAPADOPOULOS[2]證明了置換圖上的無限制性 node multicut問題是多項式可解的,且設計了時間復雜度為O(n3)的算法,其中n為圖的頂點數.

一般的multicut問題是要求所有頂點對被斷開,而有些頂點對在斷開時可能會出現選取的邊的權重很大的情況,這時需要考慮拒絕斷開這些頂點對,同時支付部分懲罰費用,這就將multicut問題拓展到了具有懲罰費用問題的層面.LIU等[6]將帶線性懲罰推廣到帶次模懲罰,引入了帶次模懲罰的樹上的多割問題,并且基于原始對偶方案給出了帶次模懲罰的樹上的多割問題的一個3-近似算法.HOU等[7]研究了樹上具有懲罰費用的k-edge multicut問題,該問題推廣了樹上邊multicut問題,并運用線性規劃理論和拉格朗日松弛技巧設計了近似值為(4+ε)的算法,其中ε為任意固定正數.侯鑫[8]研究了樹上的k-獎勵收集多割問題和樹上的P獎勵收集多割問題,對于樹上k-獎勵收集多割問題和樹上的P獎勵收集多割問題,設計了求解其近似值為(4+ε)的算法,其中ε為任意固定正數.侯晨菲[9]主要研究了與次模函數有關的樹上多割問題.這些文獻重點研究了不同類型的具有懲罰費用的邊multicut 問題,但對于圖而言,要分離圖上的頂點,可以去掉圖上的邊,也可以去掉圖上的頂點,而這些文獻對于具有懲罰費用的點multicut 問題的研究較少.本文提出具有懲罰費用的限制性node multicut問題,為了得到很好的結果,將問題限制在樹上進行研究.

1 樹上具有懲罰費用的限制性node multicut問題

樹上具有懲罰費用的限制性node multicut問題是指:給定頂點賦權樹T=(V,E;w)及頂點V的k個頂點對構成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每個終端點對{si,ti}都有一個非負的懲罰費用pi,求T的一個頂點子集D,使得D滿足D中不含S中的點且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通,其中T[V-D]表示T的由頂點集V-D導出的子圖.目標是使D中頂點的權重之和與在T[V-D]中未斷開的頂點對的懲罰費用之和最小.

樹上限制性node multicut問題是指:給定頂點賦權的樹T=(V,E;w)及頂點V的k個頂點對構成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,求T的一個頂點子集D,使得D滿足D中不含S中的點且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通.目標是使D中頂點的權重之和最小.

S中的點稱為終端點,若S中的點對{si,ti}的懲罰費用非常大,超過斷開此點對所選非終端頂點的權重之和,此時只能斷開S中所有點對,則樹上具有懲罰費用的限制性node multicut問題化為樹上限制性node multicut問題,因此該問題作為樹上限制性node multicut問題的推廣形式是NP完備的.

下面介紹如何將樹上具有懲罰費用的限制性node multicut問題歸約到樹上限制性node multicut問題,并利用線性規劃及對偶理論設計算法進行求解.

任給樹上具有懲罰費用的限制性node multicut問題的一個實例I:給定頂點賦權的樹T=(V,E;w)及頂點V的k個頂點對構成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每個終端點對{si,ti}都有一個非負懲罰費用pi,求T的一個頂點子集D,使得D滿足不含S中的點且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通.目標是使D中頂點的權重之和與在T[V-D]未斷開的頂點對的懲罰費用之和最小.

下面證明實例I與實例τ(I)的解是等價的,若D是實例I的解,在T[V-D]中未被斷開的頂點對要支付懲罰費用,假設被懲罰的所有頂點對的下標構成的集合為N,即N={i|?pi∈T[V-D],si,ti∈pi, ?{si,ti}∈S},其中

與實例I的目標函數值一致.

反之,若D′是實例τ(I)的解,即S′中所有頂點對在T′[V′-D′]中都不連通,令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},則N={i|ti″∈D″},則D是實例I的解,下標在N中的頂點對集合是在T[V-D]中未斷開的集合,此時實例I與實例τ(I)的目標函數值一樣,因此根據上述描述任給樹上具有懲罰費用的限制性node multicut問題的一個實例I都可以轉化成樹上限制性node multicut問題的一個實例τ(I),它們的解可以相互轉換,且目標函數值相同.

下面介紹如何利用線性規劃的相關理論知識設計求解實例τ(I)的算法,并將算法求得的解轉化為實例I的解,并證明轉化回來的解的近似值.

2 原始-對偶算法

用0-1整數規劃來描述實例τ(I).

對V′-S′中的每一個頂點引入布爾變量xv,用來表示頂點v是否在集合D′中,若v?D′,則令xv=0,若v∈D′,則令xv=1.P′i表示在樹T′中si到t′i之間的路,因為T′是樹,因此si到t′i之間的路是唯一的,此時得到實例τ(I)的0-1整數規劃,記為IP.

因為整數規劃的求解是NP難的,因此對上述整數規劃進行松弛,就得如下的線性規劃記為LP.

算法的思想:從原始線性規劃的一個不可行解?v∈V′-S′,xv=0及對偶線性規劃的一個平凡可行解fi, ?i∈{1,2,…,k}開始,在每一次迭代過程中保證對偶線性規劃的解的可行性,然后逐步調整原始線性規劃的解和對偶線性規劃的解,使得原始線性規劃的解盡可能滿足可行性,而對偶規劃的解盡可能滿足最優性,直到調整到原始線性規劃的解滿足可行性.

算法具體步驟如下:

輸出:斷開頂點對所選的非終端點構成的集合D′

步驟1 令fi=0, ?i∈{1,2,…,k},D′=?.

步驟2 任取T′的一個頂點作為根節點,假設為v0.

步驟3 計算V′中每一個頂點的深度,即對?v∈V′(T′)計算頂點v的深度d(v),d(v)表示v到v0的唯一路上邊的數目.

步驟4 將步驟3計算得到的所有頂點的深度d(v)從大到小進行排序,d(vn)≥d(vn-1)≥…≥d(v0).

輸出:fi,?i∈{1,2,…,k}及集合D′.

若v∈D′,令xv=1,否則令xv=0,于是上述算法輸出的解xv,?v∈V′-S′及fi,?i∈{1,2,…,k}分別為松弛線性規劃和對偶規劃的可行解,于是得到如下結論:

根據文獻[10]的性質5得出上述原始線性規劃和對偶線性規劃的可行解,滿足的互補松弛條件是:

(5)

圖1 si0到的路及si到ti的路

將上述算法求得的實例τ(I)的解D′,轉化成實例I的解,轉化方式為:令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},則N={i|ti″∈D″}.于是得到如下定理.

證明

(6)

(7)

(8)

(9)

定理5令OPT,O′PT分別是實例I和實例τ(I)的最優解的值,調用原始-對偶算法求解的實例τ(I)的解轉化成實例I的解,則所得的解的近似值為2.

證明 算法求得的實例τ(I)的解為D′,轉化成實例I的解為D,N,其中,D為斷開終端點對所選的非終端點集合,N為在T-D中未斷開的頂點對的下標構成的集合,因此實例τ(I)的最優解可以轉化成實例I的一個可行解,故O′PT≤OPT,于是,再由定理3和定理4得到:

綜上所述,D中頂點的權重之和與在T[V-D]未斷開的頂點對的懲罰費用之和小于等于最優解的2倍,因此這樣求得的解D,N的近似值為2.

3 結語

本文研究了樹上具有懲罰費用的限制性node multicut 問題,將該問題轉化成樹上限制性node multicut 問題,并利用線性規劃和對偶規劃的相關理論設計了近似值為2的算法.下一步將重點研究更多特殊圖上的具有懲罰費用的限制性node multicut 問題及其各種推廣問題.