樹上限制性k-node multi-multiway cut 問題的近似算法

楊 惠 娟

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

1 樹上限制性k-node multi-multiway cut 問題

樹上限制性k-node multi-multiway cut問題是指任意給定樹T=(V,E;w)以及正整數(shù)k和頂點V的q個頂點子集構成的集合S={S1,S2,…,Sq}，對?i∈{1,2,…,q},Si?V,其中w:V-S→R+,目標是求G的一個頂點子集D，使得D滿足如下條件:

(1)對?i∈{1,2,…,q},D不含Si中的點。

(2)S中至少有k個子集在G-D中不連通。

D稱為限制性node multi-multiway cut。Si稱為終端集，Si中的點稱為終端點。根據(jù)定義要求每個Si是獨立集。

若對?i∈{1,2,…,q}，都|Si|=2，則此問題轉(zhuǎn)化為限制性k-node multicut問題；若k=q=1此問題轉(zhuǎn)化為限制性node multicut問題。

下面通過將k-嚴格頂點覆蓋問題歸約到此問題來說明它們具有相同的近似比。

k-嚴格頂點覆蓋(k-SVC)是指給定一個無向圖G=(V,E)及正整數(shù)k，目標是求G的一個頂點子集，使得由這個頂點子集導出的子圖至少有k條邊[8]。

定理1 若k-嚴格頂點覆蓋問題存在近似值為α的多項式時間算法，則調(diào)用此算法可得到樹上限制性k-node multi-multiway cut問題的近似值也為α。

例 已知k-嚴格頂點覆蓋(k-SVC)的實例I及按照定理的構造方式得到k-node multi-multiway cut問題的一個實例τ(I)如下：

這3個終端集對應了實例I中的3條邊(v1,v3)、(v1,v5)、(v3,v5)，而U={u1,u3,u5}對應了實例I中的頂點子集為V′={v1,v3,v5}，且G[V′]中恰好有3條邊(v1,v3)、(v1,v5)、(v3,v5)。

2 樹上限制性k-node multi-multiway cut問題的近似算法

本節(jié)主要介紹如何運用貪心策略和線性規(guī)劃理論的LP-rounding技術設計問題的近似算法。

2.1 貪婪策略

另一方面，由于樹上的限制性node multiway cut 問題可以用動態(tài)規(guī)劃在多項式時間內(nèi)求得最優(yōu)解。因此為了降低近似比，將原問題分解成q個樹上的限制性node multiway cut 問題進行求解，求得每一個子問題的最優(yōu)解，然后按上述方式找出前k個權重最小的頂點子集，就得到原問題的一個可行解，并且此可行解的近似值為k。

2.2 LP-rounding技術

下面用0-1整數(shù)規(guī)劃來描述樹上的限制性k-node multi-multiway cut問題。

設D表示樹上限制性k-node multi-multiway cut。變量xv∈{0,1}表示頂點v是否屬于D。若xv=0表示頂點v不在D中，若xv=1表示頂點v在D中，Pi表示終端集Si中所有點之間的路集合，因為樹上任意兩點之間只有唯一的一條路，故|Pi|≤2|Si|，變量zi∈{0,1}用來記錄終端集合Si是否斷開。因此得到如下0-1整數(shù)規(guī)劃，記為IP：

(1)

(2)

xv∈{0,1}

(3)

zi∈{0,1}

(4)

0-1整數(shù)規(guī)劃的求解是NP難的，當變量數(shù)比較少時一般采用窮舉法，但是當圖的規(guī)模比較大時導致變量數(shù)比較多，用窮舉法幾乎是不可能的。

將上述0-1整數(shù)規(guī)劃轉(zhuǎn)換為松弛線性規(guī)劃記為LP：

(5)

(6)

0≤xv≤1

(7)

0≤zi≤1

(8)

(9)

(10)

xv≥0

(11)

zi≥0

(12)

上述規(guī)劃記為RLP，它的規(guī)模是多項式的，可用橢球算法[1]進行求解。設求得的最優(yōu)解用向量形式表示為(x*,z*)，若(x*,z*)中的每個分量都是整數(shù)，則為原問題的最優(yōu)解，若有些分量是分數(shù)的形式，那么將用LP-rounding技術把求得的分數(shù)解逐步調(diào)整為整數(shù)解。

調(diào)整方法如下：

上式與RLP的約束條件(11)矛盾。

(13)

則式(13)是下列線性規(guī)劃的可行解

(14)

xv≥0

(15)

上述線性規(guī)劃對應的是樹上限制性node multicut問題的分數(shù)解，設樹上的限制性node multicut問題的最優(yōu)解為OPT，調(diào)用文獻[10]算法可得樹上限制性node multicut的一個近似值為2的可行解x**，由式(13)得

于是

(16)

設原問題的最優(yōu)解為OPT1，因此滿足線性規(guī)劃RLP的所有約束條件是RLP的可行解而(x*,z*)是RLP的最優(yōu)解，從而得到

(17)

由式(16)和式(17)得

綜上所述，得如下定理：

定理2 樹上限制性k-node multi-multiway cut問題具有近似值為min{2(q-k+1),k}的算法。

3 結(jié) 語

研究了限制性k-node multi-multiway cut問題限制在特殊圖樹上的情況，并借助樹的性質(zhì)及貪心策略和線性規(guī)劃的LP-rounding技術設計了近似值min{2(q-k+1),k}的多項式時間算法。如何改進算法提高精確度及考慮更多特殊圖上的限制性k-node multi-multiway cut問題是下一步主要的研究方向。