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

楊惠娟，董延壽，林仕勛

（昭通學院 數學與統計學院，云南 昭通657000）

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

楊惠娟，董延壽，林仕勛

（昭通學院 數學與統計學院，云南 昭通657000）

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

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

1 引言

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

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

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

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

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

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

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

算法1:

輸入:T=(V,E;w)以及正整數k和q個頂點對構成的集合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}轉到第2步.

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

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

End

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

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

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

算法2:

輸入:T=(V,E;w)以及正整數k和q個頂點對構成的集合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}轉到第2步.

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

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

End

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

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

5 結論

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

〔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〕高隨祥.圖論與網絡流理論[M].北京:高等教育出版社,2009.308.

O157.5

A

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

2017-06-08

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