楊 惠 娟

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

1 樹上限制性k-node multi-multiway cut 問(wèn)題

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

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

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

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

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

下面通過(guò)將k-嚴(yán)格頂點(diǎn)覆蓋問(wèn)題歸約到此問(wèn)題來(lái)說(shuō)明它們具有相同的近似比。

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

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

例 已知k-嚴(yán)格頂點(diǎn)覆蓋(k-SVC)的實(shí)例I及按照定理的構(gòu)造方式得到k-node multi-multiway cut問(wèn)題的一個(gè)實(shí)例τ(I)如下：

這3個(gè)終端集對(duì)應(yīng)了實(shí)例I中的3條邊(v1,v3)、(v1,v5)、(v3,v5)，而U={u1,u3,u5}對(duì)應(yīng)了實(shí)例I中的頂點(diǎn)子集為V′={v1,v3,v5}，且G[V′]中恰好有3條邊(v1,v3)、(v1,v5)、(v3,v5)。

2 樹上限制性k-node multi-multiway cut問(wèn)題的近似算法

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

2.1 貪婪策略

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

2.2 LP-rounding技術(shù)

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

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

(1)

(2)

xv∈{0,1}

(3)

zi∈{0,1}

(4)

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

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

(5)

(6)

0≤xv≤1

(7)

0≤zi≤1

(8)

(9)

(10)

xv≥0

(11)

zi≥0

(12)

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

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

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

(13)

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

(14)

xv≥0

(15)

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

于是

(16)

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

(17)

由式(16)和式(17)得

綜上所述，得如下定理：

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

3 結(jié) 語(yǔ)

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