樹上的限制性node multicut問題

楊惠娟

（昭通學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，云南昭通 657000）

1 背景知識

1.1 問題的現(xiàn)實意義割集理論在圖論和組合優(yōu)化中占有舉足輕重的地位，它不僅可以用來設(shè)計精確算法，同時還被用來設(shè)計一些問題的近似算法。而且它在現(xiàn)實中的應(yīng)用也是非常廣泛的，特別是在城市建設(shè)、道路規(guī)劃等方面。原始的最小割集問題是指給定一個連通的邊賦權(quán)圖G 以及在G 中指定兩個點s,t。目標(biāo)是找G 的一個最小權(quán)重的邊子集D 使得s,t 在G-D 中不連通。對于這個問題可以用圖論中的經(jīng)典算法最大流算法〔1-2〕多項式求解并且得到了最大流最小割集定理。但是隨著對問題的不斷深入割集問題已經(jīng)產(chǎn)生了很多復(fù)雜的推廣問題，不同領(lǐng)域的研究者已經(jīng)對這些問題做了研究并得到了一些相應(yīng)的成果。

1.2 Multicut 問題的研究現(xiàn)狀Multicut 問題分為edge multicut問題和node multicut問題。

edge multicut 問題：是指給定一個連通邊賦權(quán)圖G=(V,E;w)以及由G 中頂點構(gòu)成的k 個頂點對集合S，即 S={(s1,t1),(s2,t2),…，(sk,tk)}，D 是 G 的一個邊子集，如果S 中的每一個頂點對在G-D 中不連通，則稱D 為G 的edge multicut。目標(biāo)是求G 的最小權(quán)重的edge multicut D ，即

node multicut 問題：是指給定一個連通邊賦權(quán)圖G=(V,E;w)以及由G 中頂點構(gòu)成的k 個頂點對集合S，即 S={(s1,t1),(s2,t2),…,(sk,tk)}，G 的一個頂點子集D，如果D 滿足S 中的每一個頂點對在G-D 中不連通，則稱D 為G 的node multicut。目標(biāo)是求G 的最小權(quán)重的 node multicut D，即

如果去掉的頂點集合D 中允許有S 中的點則稱node multicut為無限制node multicut問題，如果去掉的頂點集合D 中不允許有S 中的點則稱node multicut 問題為限制性node multicut 問題。無限制node multicut問題可以多項式的歸約到限制性node multicut問題，因為任給無限制node multicut 問題的一個實例I ，對實例I 中每一個頂點對(si,ti)構(gòu)造一個新的頂點對及兩條新的邊，然后將新的k 個頂點對構(gòu)成的集合作為限制性node multicut 問題中考慮的k 個頂點對。通過這種變換就得到了限制性node multicut問題的一個實例。

根據(jù)所給的連通賦權(quán)圖G 是有向的或是無向的，multicut 問題也有4 種形式分別為：有向圖的edge multicut 問題〔3-4〕，無向圖的 edge multicut 問題，有向圖的node multicut 問題，無向圖的node multicut 問題。

當(dāng)k=1 時，edge multicut 問題一樣都是割集問題，所以可以利用最大流算法求解。

當(dāng) k=2 時，Hu〔5〕中說明了上述4種形式的multicut問題是多項式可解的。

當(dāng) k ≥3 時，Dahlhaus 等在文獻〔6〕中證明了一般圖上的edge multicut 問題是NP 完備的并且不能得到一個PTAS，除非P=NP，同時他給出了一個近似值為 O(log k)的算法。Chawla 和 Krauthgamer〔7〕證明了要想得到這個問題的一個常數(shù)近似算法是NP難的并且提出猜想: 這個問題是Ω(log log ||V )不可近似的。對于一般圖上的node multicut 問題，Garg和Vazirani〔8〕給出了一個近似值為O(log k)的算法。

一般圖上multicut 問題的求解是非常難的，很多研究者將它限制在特殊圖上進行研究，得到了一些很好的成果。樹上的edge multicut 問題，Garg 和Vazirani〔9〕通過最小點覆蓋問題歸約到此問題，從而說明它是NP 完備，并且設(shè)計了近似值為2 的算法。Costa 等〔10〕給出了一個貪婪算法在多項式時間內(nèi)找到了根樹上的edge multicut 問題的最優(yōu)解。Calinescu 等〔11〕主要研究了無賦權(quán)且滿足度限制和樹寬度限制的圖上的node multicut問題并做出了如下成果：

（1）在樹寬度至多為2 的圖上無限制的node multicut 問題是NP 難的并且當(dāng)圖滿足樹寬度限制時，無限制的node multicut問題存在PTAS。

（2）證明了有向edge multicut 問題在滿足樹寬度是1和圖的最大出度與入度都為3的有向圖中是NP 難的。

（3）樹上當(dāng)頂點的權(quán)重是1 時無限制的node multicut問題是多項式可解的。

Guo 和Huffner 等在文獻〔9〕中證明了區(qū)間圖上的無限制性node multicut 是 NP 難的，限制性的node multicut 是多項式可解的。Papadopulos〔12〕研究了置換圖上的限制性node multicut問題并且給出了一個多項式時間算法。

對于樹上的 k-edge multicut 問題 Mestre〔13〕設(shè)計了一個近似值為2+ε 的近似算法，樹上推廣的kedge multicut 問題文獻〔14〕中設(shè)計了一個近似值為O(q)的近似算法。

2 樹上的限制性node multicut問題

定義1任給一個連通邊賦權(quán)樹T=(V,E;w)以及由T 中頂點構(gòu)成的k 個頂點對集合S，即S={(s1,t1),(s2,t2),…,(sk,tk)}，其中 w:V-S → R+，目標(biāo)是求 G 的一個頂點子集D，并且D 滿足如下條件：

（1）D 中不含 S 中的點；

（2）S 中的每一個頂點對在T-D 中不連通；

首先說明這個問題是NP 完備的。方法是通過樹上的edge multicut問題歸約到此問題。任給樹上的edge multicut問題的實例I：T=(V,E;w)，S={(s1,t1),(s2,t2),…,(sk,tk)}，其中 w:E →R+，目標(biāo)是求 T 的一個權(quán)重最小的邊子集 D ，即，使得 S中的每一個頂點對在T-D 中不連通，其中D 稱為T 的edge multicut。構(gòu)造樹上的限制性node multicut 問題的一個實例τ(I)，構(gòu)造方法：在T 的每一條邊上插入一個點，這個新插入的點的權(quán)重為它所在這條邊的權(quán)重，而原圖T 中不在S 中的點的權(quán)重為無窮大的數(shù)（至少是T 中所有邊的權(quán)重之和的c(c ＞1)倍），這樣得到的就是樹上的限制性node multicut 問題的一個實例。如果有一個算法A 能夠解決τ(I)那么它也能解決實例I 。因為通過算法A 求得的τ(I)的解D 中是不可能含有原圖T 中的任何一個頂點，它只能含有新構(gòu)造的點，所以D 中這些點對應(yīng)到原圖T 中邊的集合就是實例I 的解。因此樹上的限制性node multicut問題是NP 完備的。

下面用線性規(guī)劃來描述樹上的限制性node multicut問題。

令D 表示此問題的限制性node multicut，dv表示頂點v 是否屬于D，如果v 屬于D 則dv=1，否則dv=0。因為樹上的任意兩個點之間只有唯一的一條路，所以S 中的每一頂點對si到ti(i=1,2,3,…,k)的唯一的路用Pi來表示。則原始線性規(guī)劃如下：

它的松弛線性規(guī)劃用RLP：

對S 中的每一頂點對(si,ti)對應(yīng)的路Pi引進一個變量 fi，fi可以理解為分配在Pi上的一個多物種流，則RLP 的對偶線性規(guī)劃為如下的DRLP：

則松弛以后的互補松弛條件如下：

原始互補松弛條件：對每一個v ∈V-S,dv≠0，則

松弛以后的對偶互補松弛條件：對每一個i ∈{1,2,3,…,k}，fi≠ 0，則

算法思想是：先找一個滿足原始松弛條件的可行解，然后在保證每一步都是可行解的條件下，一步步的調(diào)整這個解，使得它逐步向松弛以后的對偶互補松弛條件靠近，最終滿足松弛的對偶互補松弛條件。具體算法如下。

輸入：T=(V,E;w)以及由T 中頂點構(gòu)成的k 個頂點對集合 S ，即 S={(s1,t1),(s2,t2),…,(sk,tk)} ，其中w:V-S → R+；

輸出：限制性的node multicut D和{f1,f2,f3,…,fk}。

Begin

步驟1：令 f1=f2=f3=…=fk=0，D=φ；

步驟2：對S 中的每一個頂點對(si,ti)考慮si到ti的路Pi，檢查Pi上的點是否全是S 中的點，如果是則輸出：此問題無可行解，否則轉(zhuǎn)步驟3；

步驟3：因為樹T 是無向的，所以可以任取一點作為樹的根結(jié)點，假設(shè)這個點為v0，對T 中的每一個頂點v 計算depth(v)，depth(v)表示的是點v 到根結(jié)點v0的路P 上的邊的數(shù)目；

步驟4：將步驟3 計算得到的depth(v)按從大到小的順序進行排序記為：depth(v1)≥depth(v2)≥depth(v3)≥… ≥depth(vm)；

步驟5：按步驟4的順序考慮每一個頂點vi，假設(shè)已經(jīng)考慮完前面k 個點，則下一步考慮vk+1，當(dāng)考慮到vk+1時，先找出S 中所有使得lca(si,ti)=vk+1的頂點對(si,ti)，其中l(wèi)ca(si,ti)表示的是一個點它滿足這樣的性質(zhì)即它是si到根節(jié)點v0的路與ti到根節(jié)點v0的路的第一個交點。在每一個頂點對對應(yīng)的路Pi上最大限度的分配流量，分配的方法如下：

把Pi上的所有飽和點即滿足的點按任意的順序放入D，直到使S 中滿足lca(si,ti)=vk+1的所有頂點對對應(yīng)的Pi上都最大限度的分配到流量為止，此時標(biāo)記vk+1為已經(jīng)處理的點，一直重復(fù)上述過程直到所有的點都考慮完為止，此時得到

步驟6：假設(shè)步驟5 得到的node multicut D=去掉D 中多余的點：方法是從最后一點 v′l開始，考慮 D-{v′l} 是否是T 的node multicut，即S 中的每一個頂點對在(T-D-{v′l})中不連通，則 D:=D-{v′l}，否則繼續(xù)考慮下一個點直到D中所有的點都考慮完為止；

步驟7：輸出{f1,f2,f3,…,fk}和D。

End

算法正確性分析：在算法步驟5 保證了每一個頂點對(si,ti)的路Pi上至少有一個點被飽和也就是每一條路Pi上至少有一個點被選進D 中，所以步驟5 結(jié)束得到的D 是node multicut。步驟6 是在保證 D 是node multicut 的條件下去掉 D 中多余的點。因此整個算法結(jié)束就得到D 是node multicut。

算法的時間復(fù)雜度分析：在步驟4 涉及到的排序用二分法來實現(xiàn)時間復(fù)雜度為O(n log n)。在步驟5 中對每一個頂點都考慮至多有n 個頂點，而每個頂點要考慮它的頂點對至多有k 個頂點對，這一步的時間復(fù)雜度為O(nk)，所以總的時間復(fù)雜度為O(max{kn,n log n})。

定理1 令si,ti是一對有非零流量的頂點對（ fi≠ 0）且 lca(si,ti)=vi是 node multicut，設(shè) si到vi的路為 Pi1，ti到vi的路為 Pi2則有：

證明：假設(shè) |D ?V(Pi1) |=2，即算法結(jié)束后得到的D 中有 Pi1上的兩個點，分別設(shè)為 v 和 u ，且depth(v)≥depth(u)。假設(shè)算法在步驟5中先考慮的是點v（同理也可以假設(shè)考慮的點是u）v 在D。當(dāng)考慮到u時因為u 在步驟5 時沒有被刪除，所以在S 中必須有一個頂點對(sj,tj) 使得u 是 Pj在 D 中的點且lca(sj,tj) =depth(vj) 且 depth(vj)≥depth(u)。 在考慮 vj時如果u 在這時被選入D，那么考慮到vi時Pi上已經(jīng)有飽和點u，此時分配在Pi上的流量為0，這與 Pi是流量路矛盾。如果在此時u 未被選入D 那么在Pj中一定有另外的點u0被選入，在這種情況下算法步驟6 首先考慮的是u，則此時u一定會從D中被刪除，這就產(chǎn)生矛盾。

從上面的分析可知，算法得到的解{f1,f2,f3,…,fk}和D 分別是RLP 和DRLP 的可行解，且滿足松弛以后的互補松弛條件，因此算法得到的近似值為2。下面我們進一步說明算法得到的解是RLP 和DRLP 的最優(yōu)解，且具有半整數(shù)的性質(zhì)。因為任何一條流量路上至多只有兩個點在D 中，設(shè)Pi和Pj是兩條流量路且u,v 是Pi在D 中的兩個點，u′是Pj在 D 中的唯一的點，那么一定有 u ≠u′且 v ≠u′。否則假設(shè)有u=u′或者v=u′在這里只分析u=u′的情況，對于另一種可以同理說明。由算法步驟5 和步驟6 可知無論是選入D 的點還是從D 中刪除的點都是按順序進行操作的，所以當(dāng)u=u′成立時，我們分為以下兩種情況討論：

（1）在算法步驟5頂點對(sj,tj)先于頂點對(si,ti)被考慮這有兩種可能：

如果此時u=u′被選入D，那么當(dāng)考慮到頂點對(si,ti)時Pi上已經(jīng)有飽和點u=u′，此時流量的增加值θ 就為0，這與Pi是流量路矛盾。

如果在考慮頂點對(sj,tj)時u=u′未被選入D中，此時一定有Pj上異于u′的點u″被選入 D 中點u′是在考慮后面某一頂點對的時候才被選入，那么算法步驟6先考慮的點是 u′而 D-{u′}是node multicut這與u′是Pj在D 中的唯一點矛盾。

（2）在算法步驟5頂點對(si,ti)先于頂點對(sj,tj)被考慮，此時如果u′被選入則與Pj是流量路矛盾，所以只能是v 被選入。如果不存在另外一個頂點對(sk,tk)使得v 是流量路Pk在D 中的點那么在算法步驟6，v 一定被刪除因為D-{v}是node multicut這就產(chǎn)生矛盾。但是即使v 是流量路Pk在D 中的點這也與Pi是流量路或者v 在D 中矛盾。

綜上所述：在D 中只有一個點的流量路和在D中有兩個點的流量路在D 中的點是不同的。因此可以按如下方式構(gòu)造RLP 的解對每一條流量路Pi，如果 Pi在 D 中有兩個點 u,v 則 du=dv=1/2；如果 Pi在 D 中有一個點u 則du=1，其余除S 中的點外所有點的距離標(biāo)記為0。這樣構(gòu)造的解一定滿足當(dāng)α=β=1 時的互補松弛條件，所以它是RLP 的最優(yōu)解且具有半整數(shù)的性質(zhì)。

〔1〕拉文德拉K.阿胡亞，托馬斯L.馬南提，詹姆斯B.沃琳，等.網(wǎng)絡(luò)流理論算法與應(yīng)用〔M〕.北京:機械工業(yè)出版社，2005:207-240.

〔2〕劉振宏，蔡茂誠. 組合最優(yōu)化:計算機算法和復(fù)雜性〔M〕.北京:清華大學(xué)出版社，1988:248-269.

〔3〕STEFAN K，MARCIN P，MICHAL P.Fixed-parameter tractability of multicut in directed acyclic graphs〔J〕.Computer Science，2012（7391）:581-593.

〔4〕JORGEN B J，ANDERS Y.The complexity of multicut and mixed multicut problems in （di）graphs〔J〕. Theoretical Computer Science，2014（520）:87-96.

〔5〕HU T C.Multicommodity network flows〔J〕.Oper Res，1963（9）:898-900.

〔6〕DAHLHAUS E，JOHNSON D S，PAPADIMITRIOU C H，et al.The complexity of multiterminal cuts〔J〕.SIAM J Comput，1994，23（4）:864-894.

〔7〕CHAWLA S，KRAUTHGAMER R，KUMAR R，et al. On the hardness of approximating multicut and sparsestcut〔J〕.Computational Complexity，2006，15（2）:94-114.

〔8〕GARG N，VAZIRANI V，YANNAKAKIS M. Primal-dual approximation algorithms for integral flow and multicut in trees〔J〕.Algorithmica，1997（18）:3-20.

〔9〕Costa M C，Letocart L，Roupin F. A greedy algorithm for multicut and integral multiflow in rooted trees〔J〕.Operations Research Letters，2003（31）:21-27.

〔10〕CALINESCU G，F(xiàn)ERNANDES C G，REED B. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width〔J〕.Journal of Algorithms，2003（48）:333-359.

〔11〕GUO J，HUFFNER F，KENAR E，et al.Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs〔J〕.European Journal of Operational Research，2008（186）:542-553.

〔12〕CHARIS P.Restricted vertex multicut on permutation graphs〔J〕.Discrete Applied Mathematics，2012（160）:1791-1797.

〔13〕 JULIAN M.Lagrangian relaxation and partial cover（extended abstract）〔J〕.Theoretical Aspects of Computer Science，2008（25）:539-550.

〔14〕ZHANG P，ZHU D，LUAN J F.An approximation algorithm for the Generalized k-Multicut problem〔J〕.Discrete Applied Mathematics，2012（160）:1240-1247.