楊惠娟，董延壽，林仕勛

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

樹上限制性k-node multicut問題的近似算法

楊惠娟，董延壽，林仕勛

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

樹上的限制性k-node multicut問題(k-CMC(T))是NP難的,針對k-CMC(T)問題本文首先將問題分解成若干個最大流問題設(shè)計了近似值為k的算法其中k是參數(shù).其次利用樹的性質(zhì)改進算法降低了算法的時間復(fù)雜度得到一個時間度為O(|V|3log2|V|)且近似值不變的算法.算法簡單、易懂.

限制性k-node multicut；近似算法；樹；最大流

1 引言

原始的multicut問題（MC)是圖論與組合優(yōu)化中比較活躍和經(jīng)典的一類問題,原始的multicut問題分為edge multicut問題(EMC)和node multicut問題(NMC).它們在現(xiàn)實中的應(yīng)用廣泛，特別是在城市建設(shè),道路規(guī)劃,通訊等方面.近幾十年來一直受到廣泛關(guān)注,但是隨著對問題的不斷深入，許多研究者對原始的multicut問題（MC)的提法或目標進行改動，這就產(chǎn)生了一些比較復(fù)雜的推廣問題如k-edge multicut問題(k-EMC)問題和k-node multicut問題(k-NMC)問題等這些推廣問題都是NP難,因此與其花大量的時間去找一個最優(yōu)解,倒不如在多項式時間內(nèi)去找一個近似度較好的可行解.

一般圖上multicut問題及它的推廣問題的求解是非常難的,因此很多研究者將它限制在特殊圖上進行研究.Guo和Huffner等在文獻[1]中證明了區(qū)間圖上的無限制性node multicut是NP難的,限制性的node multicut是多項式可解的.Papadopulos[2]研究了置換圖上的限制性node multicut問題并且給出了一個多項式時間算法去求得最優(yōu)解.對于樹上的edge multicut問題(EMC(T))問題,Garg,Vazirani和Yannakakis在文獻[3]中利用線性規(guī)劃的原始-對偶理論設(shè)計了近似值為2的算法,這是EMC(T)問題目前最好的算法且同時證明了即使在高度為1且不賦權(quán)（圖中每一條邊的權(quán)重都是1）的樹上EMC問題都是NP難和MAX SNP難的.對于樹上限制性node multicut問題(NMC(T))問題文獻[4]中設(shè)計了一個近似比為2的算法.Levin和Segev在文獻[5]中考慮了Prize-Collecting版本的樹上的edge multicut問題(pc-EMCP(T)),他們將pc-EMCP(T)問題歸約到EMCP(T)并證明了文獻[1]中設(shè)計的算法對pc-EMCP(T)具有拉格朗日乘數(shù)保持性質(zhì).樹上的k-edge multicut問題Mestre[6]設(shè)計了一個近似值為2+ε的近似算法，樹上推廣的k-edgemulticut問題文獻[7]中設(shè)計了一個近似值為的近似算法.

2 樹上限制性k-node multicut問題的描述及近似算法

任給無向樹T=(V,E)以及正整數(shù)k和T的q個頂點對構(gòu)成的集合S={(s1,t1),(s2,t2),…,(sq,tq)},?i∈{1,2,3,…,q}，si,ti稱為終端點,對樹T的除終端點外所有的頂點賦一個非負實數(shù)w(v),樹上限制性k-node multicut問題是求G的一個頂點子集D,并且D滿足如下條件:

（1）D不含任何終端點;

（2）S中至少有k個頂點對在G-D中不連通;

我們可將此問題分解成樹上的q個最大流問題,則得到一個近似值為k的算法.

算法1:

輸入:T=(V,E;w)以及正整數(shù)k和q個頂點對構(gòu)成的集合S={(s1,t1),(s2,t2),…,(sq,tq)}，其中w:V-S→R+

輸出:該問題無解或可行解D.

Begin

第1步:?i∈{1,2,3,…,q}檢查Pi上的點是否全是S中的點，如果全是S中的點則令i∈Q若|Q|≥q-k則輸出：此問題無解否則令S'=S-{(si,ti)|i∈Q}轉(zhuǎn)到第2步.

第2步:把此問題分解成求|S'|個樹T的node multicut問題,然后對S'中的每一個頂點對(si,ti)調(diào)用一次求解最大流的Dinic算法[8]求得最小si-ti點割集Di.

第3步:?(si,ti)∈S'計算按w(Di)從小到大排序,不妨設(shè)排序為w(D1)≤w(D2)≤…≤w(D|S'|),令D=D1∪D2∪…∪Dk,輸出D.

End

定理3.1算法1得到問題的可行解,并且近似值為k.且時間復(fù)雜度為O(|V|4|E|.

證明任給樹上限制性k-node multicut問題的一個實例I,設(shè)I的最優(yōu)解為D',即S'中至少有k個頂點對在G-D'中不連通并且達到最小,不妨設(shè)(s'1,t'1),(s'2,t'2),…,(s'k,t'k)在G-D'中不連通.因為算法1的第2步調(diào)用最大流算法求得的Di是最小si-ti點割集即頂點對(si,ti)在G-Di中不連通,因此在G中去掉D至少使得(s1,t1),(s2,t2),…,(sk,tk)在G-D中不連通,于是D是k-node multicut問題的可行解.假設(shè)用最大流算法解得的最小s'i-t'i割集,i=1,2,3…,k最優(yōu)解為D*i,而D'為可行解所以有w(D*i)≤w(D'),根據(jù)算法1第3步有則w(D')≤kw(D'),因此算法1得到的解近似值為k.算法中第1步要考慮所有的路Pi最多有q條路,而每一條路所有的點都要進行檢驗每一個點檢驗一次最多有|V|個點,故第1步總的計算量為O(q|V|).第2步對s'中的每一個頂點對調(diào)用一次Dinic算法,Dinic算法的時間復(fù)雜度為O(|V|2|E|)最多調(diào)用q次,因此第2步總的計算量為O(q|V|2|E|).第3步主要在于對w(Di)進行排序,時間復(fù)雜度為O(qlog2q).S中的頂點對至多為因此算法總的時間復(fù)雜度為

因為我們考慮的圖比較特殊是樹而樹上任意兩點之間只有唯一的一條路要想頂點對(si,ti)不連通只要在Pi上去掉一個點即可,不需要花費大量時間去調(diào)用最大流算法.因此改進算法如下：

算法2:

輸入:T=(V,E;w)以及正整數(shù)k和q個頂點對構(gòu)成的集合S={(s1,t1),(s2,t2),…,(sq,tq)}，其中w:V-S→R+

輸出:該問題無解或可行解D.

Begin

第1步:令T1=T[M]即T1是T的由頂點集M導出的子圖,檢查T中Pi上的點是否全是T1中的點,如果全是T1中的點則令i∈Q若|Q|≥q-k則輸出：此問題無解否則令S'=S-{(si-ti)|i∈Q}轉(zhuǎn)到第2步.

第2步:對S'中的每一個頂點對(si,ti)所對應(yīng)的路Pi上的非終端點按權(quán)重進行升序排序.將權(quán)重最小的點放入D',若某一條Pi上有多個點權(quán)重同時小的點只需放入一個點即可.每一條路上放入D'中一個點.

第3步:對D'中的點按權(quán)重進行升序排序,不妨設(shè)排序為w(v1)≤w(v2)≤…≤w(v|S'|),令D={v1,v2,…,vk},輸出D.

End

定理3.2算法2得到問題的可行解,并且近似值為k.且時間復(fù)雜度為O(|V|3log2|V|).

證明根據(jù)算法1的證明方法可證得算法2得到的解是可行解并且近似值為k.算法第1步首先構(gòu)造由頂點集M導出的子圖T1,方法可以刪掉所有非終端點及所有與非終端點相關(guān)聯(lián)的邊,而樹T中邊的數(shù)目|E|=|V|-1,因此這一步的計算量O(|V|2),其次考慮所有的路Pi最多有q條路,而每一條路所有的點都要進行檢驗每一個點檢驗一次最多有|V|個點,故第1步總的計算量為O(q|V|).第2步的主要計算量在于對S'中的每一個頂點對(si,ti)所對應(yīng)的路Pi上的非終端點按權(quán)重進行排序,排序一次的時間復(fù)雜度為O(|V|log2|V|),總共需要迭代q次,總得計算量為O(q|V|log2|V|).第3步主要在于對D'中的點進行排序時間復(fù)雜度為O(qlog2q).S中的頂點對至多為.因此算法總的時間復(fù)雜度為:

5 結(jié)論

本文主要提出并研究了樹上限制性k-node multicut問題.首先將問題分解成若干個最大流問題設(shè)計了近似值為的算法.算法時間復(fù)雜度雖然是實例規(guī)模的多項式,但是隨著圖的規(guī)模的增大運行算法時依然浪費了大量時間.其次結(jié)合了樹的性質(zhì)改進算法降低了算法的時間復(fù)雜度得到一個時間度為O(|V|3log2|V|)且近似值不變的算法.本文所設(shè)計的兩個算法雖然近似值都是k,它是一個參數(shù)與輸入的實例規(guī)模有關(guān),因此實例不一樣近似值也就不一樣.如何進一步改進算法使算法的近似值是一個固定常數(shù)與實例的規(guī)模無關(guān)是我們今后將要努力的方向.

〔1〕J.Guo ,F.Huffner ,E.Kenar,R.Niedermeier,J.Uhlmann.Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs[J].European Journal of Operational Research 186 2008,542-553.

〔2〕Charis Papadopoulos.Restricted vertex multicut on permutation graphs [J].Discrete Applied Mathematics 1602012, 1791-1797.

〔3〕N. Garg, V. Vazirani and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees[J].Algorithmica 1997, 18, 3-20.

〔4〕楊惠娟.樹上的限制性node multicut問題[J].大理學院學報（自然科學版），2014（12）.

〔5〕Levin A,Segev D.Partial multicuts in trees [C]//Proe of the 3rd workshop on Approximation and online Algorithms(WAOA).Berlin:Springes 2005:320-333.

〔6〕Julian Mestre,Lagrangian relaxation and partial cover(extended abstract)[J].Theoretical Aspects of Computer Science,STACC 2008 ,25:539-550.

〔7〕Peng Zhang ,Daming Zhu ,Junfeng Luan.An approximation algorithm for the Generalized k-Multicut problem[J].Discrete Applied Mathematics 2012 ,160 :1240-1247.

〔8〕高隨祥.圖論與網(wǎng)絡(luò)流理論[M].北京:高等教育出版社,2009.308.

O157.5

A

1673-260X（2017）09-0007-02

2017-06-08

云南省教育廳科學研究基金項目（2016ZDX152)；昭通學院一般項目（2016xj31）