楊惠娟

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

1 背景知識(shí)

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

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

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

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

如果去掉的頂點(diǎn)集合D 中允許有S 中的點(diǎn)則稱node multicut為無(wú)限制node multicut問(wèn)題，如果去掉的頂點(diǎn)集合D 中不允許有S 中的點(diǎn)則稱node multicut 問(wèn)題為限制性node multicut 問(wèn)題。無(wú)限制node multicut問(wèn)題可以多項(xiàng)式的歸約到限制性node multicut問(wèn)題，因?yàn)槿谓o無(wú)限制node multicut 問(wèn)題的一個(gè)實(shí)例I ，對(duì)實(shí)例I 中每一個(gè)頂點(diǎn)對(duì)(si,ti)構(gòu)造一個(gè)新的頂點(diǎn)對(duì)及兩條新的邊，然后將新的k 個(gè)頂點(diǎn)對(duì)構(gòu)成的集合作為限制性node multicut 問(wèn)題中考慮的k 個(gè)頂點(diǎn)對(duì)。通過(guò)這種變換就得到了限制性node multicut問(wèn)題的一個(gè)實(shí)例。

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

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

當(dāng) k=2 時(shí)，Hu〔5〕中說(shuō)明了上述4種形式的multicut問(wèn)題是多項(xiàng)式可解的。

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

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

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

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

（3）樹上當(dāng)頂點(diǎn)的權(quán)重是1 時(shí)無(wú)限制的node multicut問(wèn)題是多項(xiàng)式可解的。

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

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

2 樹上的限制性node multicut問(wèn)題

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

（1）D 中不含 S 中的點(diǎn)；

（2）S 中的每一個(gè)頂點(diǎn)對(duì)在T-D 中不連通；

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

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

令D 表示此問(wèn)題的限制性node multicut，dv表示頂點(diǎn)v 是否屬于D，如果v 屬于D 則dv=1，否則dv=0。因?yàn)闃渖系娜我鈨蓚€(gè)點(diǎn)之間只有唯一的一條路，所以S 中的每一頂點(diǎn)對(duì)si到ti(i=1,2,3,…,k)的唯一的路用Pi來(lái)表示。則原始線性規(guī)劃如下：

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

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

則松弛以后的互補(bǔ)松弛條件如下：

原始互補(bǔ)松弛條件：對(duì)每一個(gè)v ∈V-S,dv≠0，則

松弛以后的對(duì)偶互補(bǔ)松弛條件：對(duì)每一個(gè)i ∈{1,2,3,…,k}，fi≠ 0，則

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

輸入：T=(V,E;w)以及由T 中頂點(diǎn)構(gòu)成的k 個(gè)頂點(diǎn)對(duì)集合 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：對(duì)S 中的每一個(gè)頂點(diǎn)對(duì)(si,ti)考慮si到ti的路Pi，檢查Pi上的點(diǎn)是否全是S 中的點(diǎn)，如果是則輸出：此問(wèn)題無(wú)可行解，否則轉(zhuǎn)步驟3；

步驟3：因?yàn)闃銽 是無(wú)向的，所以可以任取一點(diǎn)作為樹的根結(jié)點(diǎn)，假設(shè)這個(gè)點(diǎn)為v0，對(duì)T 中的每一個(gè)頂點(diǎn)v 計(jì)算depth(v)，depth(v)表示的是點(diǎn)v 到根結(jié)點(diǎn)v0的路P 上的邊的數(shù)目；

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

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

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

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

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

End

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

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

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

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

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

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

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

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

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

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

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

〔2〕劉振宏，蔡茂誠(chéng). 組合最優(yōu)化:計(jì)算機(jī)算法和復(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.