超圖上最小邊覆蓋問題的算法研究

林雯 王嘉寶 陳智斌

(昆明理工大學(xué)理學(xué)院,昆明,650000)

1 引言

超圖上最小邊覆蓋問題是一個NP難問題.首先我們引入超圖的定義[1]:超圖H=(V,E),其中V是一個有限集合,E是V的子集族,V中的元素稱為超圖H的頂點(diǎn),E中的元素稱為超圖H的超邊.給定邊集C,C?E,若H中的任意一個頂點(diǎn)都在C的某條邊內(nèi),則邊集C稱為一個邊覆蓋.在這種情況下,有時也稱為邊集C能覆蓋H中的所有頂點(diǎn).給定超圖H,其中包含邊數(shù)最少的邊覆蓋稱為最小邊覆蓋.超圖上最小邊覆蓋問題即求給定超圖H上的最小邊覆蓋.超圖上最小邊覆蓋問題等價于最小集合覆蓋問題[2],最小集合覆蓋問題在1972年首次由Karp[3]提出,因此一般可將求解最小集合覆蓋問題的算法應(yīng)用于超圖上最小邊覆蓋問題.Crawford基于元啟發(fā)式方法在2013年和2014年分別提出了人工蜂群算法和文化算法求解集合覆蓋問題[4,5,6].2017年,Haddadi等對于該問題提出了分支定界法[7].以上方法在最壞情況下都是指數(shù)時間.雖然對于該問題無法求出精確解,但設(shè)計多項(xiàng)式時間近似算法得到問題近似解是可行的.Vazirani運(yùn)用原始對偶模式給出了集合覆蓋問題的f近似算法[8],其中f表示集合中最頻繁元素的頻數(shù)?同時,還提出了貪心算法求解該問題,達(dá)到Hs=1++···+的近似比,其中s表示集合的總個數(shù).

以上問題可認(rèn)為是不帶權(quán)重的,本文考慮超圖帶權(quán)重版本,即上述問題的一個推廣問題.假設(shè)H=(V,E)為一個超圖,令w:E→Z+是一個權(quán)重函數(shù),從而得到一個邊賦權(quán)超圖,記為Hw=(V,E;w).對任意的邊集C?E,定義w(C)=w(e),即邊集C在權(quán)重函數(shù)w下的權(quán)重.邊賦權(quán)超圖上的最小邊覆蓋問題即要求給定超圖H=(V,E)在邊賦權(quán)函數(shù)w:E→Z+下的一個邊覆蓋C,使得w(C)盡可能小.易知,超圖上的最小邊覆蓋問題為邊賦權(quán)超圖上的最小邊覆蓋問題的一個特殊情況,即每條邊權(quán)重均為1的情形.

本文首先針對邊賦權(quán)超圖最小邊覆蓋問題采用分層算法設(shè)計近似算法,達(dá)到f近似比.再對邊賦權(quán)拉米納超圖,設(shè)計求解最小邊覆蓋問題的精確算法,首先構(gòu)造對應(yīng)的有根樹[9],然后利用有根樹的特殊性,基于動態(tài)規(guī)劃的思想[10],對樹從下往上按層次遍歷各節(jié)點(diǎn)[11],求解出邊賦權(quán)拉米納超圖上的最小邊覆蓋.

2 邊賦權(quán)超圖最小邊覆蓋問題

2.1 問題描述

考慮邊賦權(quán)超圖最小邊覆蓋問題,給定邊賦權(quán)超圖Hw=(V,E;w),w:E→Z+,其中V是一個有限集合,V中的元素v1,v2,···vn為超圖Hw的n個頂點(diǎn),E是V的子集族,E中的元素e1,e2,···em為超圖Hw的m條超邊.邊賦權(quán)超圖最小邊覆蓋問題是指找到圖上的一個邊集C?E,使得C能覆蓋圖Hw中的所有頂點(diǎn),且w(C)=w(e)盡可能小.Hw中任何一個使得w(C)最小的邊覆蓋C稱為最優(yōu)邊覆蓋.若C?為最優(yōu)邊覆蓋,稱w(C?)為最優(yōu)值,記為OPT(Hw)=w(C?),簡記為OPT,即OPT=min{w(C)|C為邊賦權(quán)超圖Hw=(V,E;w)的邊覆蓋}.

2.2 分層算法

利用分層算法求解邊賦權(quán)超圖最小邊覆蓋問題,其思想在于將超邊集給定的權(quán)函數(shù)分解為關(guān)于超圖的導(dǎo)出子圖的一系列函數(shù).首先,參照文獻(xiàn)[8]中的表述,我們給出下面的定義和引理.

定義1給定邊賦權(quán)超圖Hw=(V,E;w),w:E→Z+,w(e)是關(guān)于超圖Hw的邊權(quán)重函數(shù),若存在常數(shù)c＞0,使得w(e)=c·|e|,則稱w(e)=c·|e|為邊加權(quán)函數(shù),其中|e|表示邊e中的元素個數(shù).

邊加權(quán)函數(shù)在求解邊賦權(quán)超圖最小邊覆蓋問題中的重要性由下述引理可知.

引理1給定邊賦權(quán)超圖Hw=(V,E;w),w:E→Z+,若w(e)是超圖的邊加權(quán)函數(shù),則w(E)≤f·OPT,其中f表示構(gòu)成E的集合中出現(xiàn)最多次頂點(diǎn)的次數(shù).

證明假設(shè)常數(shù)c滿足w(e)=c·|e|,C?是超圖Hw的最優(yōu)邊覆蓋,OPT是C?對應(yīng)的最優(yōu)值.由于C?覆蓋Hw的所有頂點(diǎn),故有

由每個頂點(diǎn)至多在f條邊中,有

進(jìn)而有

引理1得證.

定義2給定邊賦權(quán)超圖Hw=(V,E;w),w:E→Z+,從圖中刪除元素為空的邊,然后在剩余邊上計算c=min{w(e)/|e|},則稱t(e)=c·|e|為最大邊加權(quán)函數(shù).稱w′(e)=w(e)?t(e)為剩余權(quán)函數(shù).

下面用分層算法在給定超圖Hw上執(zhí)行迭代.首先從圖中刪除元素為空的邊,即|e|=0的邊,然后在剩余邊上計算c=min{w(e)/|e|},最大加權(quán)函數(shù)t(e)和剩余權(quán)函數(shù)w′(e).記D為元素為空的邊集,W為剩余權(quán)為0的邊集,P為包含集合D和W中頂點(diǎn)的點(diǎn)集.然后通過算法將超圖Hw一層一層變成它原圖的導(dǎo)出子圖.

Algorithm1分層算法1:令Hw0(V0,E0)=Hw(V,E),C=?,p=0 2:while Ep中存在元素非空的邊do 3:計算cp=min{wp(e)/|e|p},tp(e)和w′p(e),將w′p(e)=0的邊添加到Wp中?刪除Ep的空邊,將其原邊添加到Dp中,將Wp與Dp的頂點(diǎn)添加到Pp中4:Hwp+1←Hwp[Ep?(Dp∪Wp)],Hwp+1為Hwp的導(dǎo)出子圖,從Ep中刪除Pp包含的頂點(diǎn)和Dp∪Wp包含的邊,得到Ep+1,w′p+1(e)←w′p(e),|e|p+1←|e|p,p←p+1 5:end while 6:輸出邊覆蓋C=r?1∪p=0 Wp

定理1分層算法是一個關(guān)于邊賦權(quán)超圖最小邊覆蓋問題的近似算法,近似比為f.

證明首先證明C是超圖Hw的邊覆蓋.假設(shè)C不是Hw的邊覆蓋,那么C不能覆蓋Hw的所有頂點(diǎn),則至少有一個頂點(diǎn)在Dp中,這與Dp中只包含空邊相矛盾.

再證明w(C)≤f·OPT.設(shè)C?是最優(yōu)邊覆蓋,考慮邊e∈C,當(dāng)p≤q時,若有e∈Wq(q=0,1,2,···,r?1),則可以將該邊的權(quán)分解為余權(quán)函數(shù)為零的點(diǎn)集,最終得到超圖的邊覆蓋為

同時考慮e∈E?C,若e∈Dq,則邊e的權(quán)滿足以下不等式,

其中OUT表示算法得到的輸出值.定理得證.

2.3 緊例子

例1給定邊賦權(quán)完全二部圖Kf,f(見圖1),其中有2f個頂點(diǎn),f2條邊,每條邊上的權(quán)重均為1.分層算法選取圖上f2條邊作為輸出解,OUT=f2,而最優(yōu)解是邊集{{v1,u1},{v2,u2},···,{vf,uf}},OPT=f,即OUT=f·OPT.

圖1 邊賦權(quán)完全二部圖Kf,f

例2給定邊賦權(quán)超圖Hw,其中V={v1,v2,···,vn},E={{v1,v2,···,vf},{v2,v3,···,vf+1},···,{vn,v1,···,vf?1}},每條邊包含f個頂點(diǎn),每條邊的權(quán)重均為1,分層算法選取圖上所有邊,OUT=n,而最優(yōu)解C?={{v1,v2,···,vf},{vf+1,vf+2,···,v2f},···,{vn?f+1,vn?f+2,···,vn}},OPT=n/f,即OUT=f·OPT.

3 邊賦權(quán)拉米納超圖最小邊覆蓋問題

3.1 邊賦權(quán)拉米納超圖

定義3([12])給定邊賦權(quán)超圖Hw=(V,E;w),w:E→Z+,其中n個頂點(diǎn)分別為v1,v2,···,vn,m條超邊分別為e1,e2,···,em,若超圖的邊滿足:ei∩ej=?或ei?ej或ej?ei(i,j=1,2,···,m),則稱該邊賦權(quán)超圖為邊賦權(quán)拉米納(Laminar)超圖.

3.2 邊賦權(quán)拉米納超圖最小邊覆蓋算法

3.2.1 構(gòu)造有根樹

為了構(gòu)造有根樹,我們先給出如下幾個定義.

定義4([15])對于一顆有向樹,若恰有一個頂點(diǎn)入度為0,其余頂點(diǎn)入度為1,則稱此有向樹為有根樹.

定義5([16])如果一個集合ei中的每一個元素都在集合ek中,且ek中可能包含ei中沒有的元素,則稱ek為ei的一個超集.

現(xiàn)在針對拉米納超圖Hw=(V,E;w),w:E→Z+,介紹構(gòu)造有根樹T=(U,A;w)的方法.有根樹的節(jié)點(diǎn):(1)邊集E中的每條超邊ei作為節(jié)點(diǎn)?(2)在T中用e0表示V,e0作為根節(jié)點(diǎn),樹T的節(jié)點(diǎn)集為U=E∪e0.在樹T中,對任意節(jié)點(diǎn)ei∈E,權(quán)重表示為wei,對于節(jié)點(diǎn)e0,令we0=+∞.

關(guān)于有根樹T中的邊集,我們有:(1)若ei在E?ei中無超集,則存在一條e0到ei的有向邊(e0,ei).(2)若ei?ek,且不存在j∈{1,2,···m}{i,k}使得ei?ej?ek,則存在一條ek到ei的有向邊(ek,ei)(k=1,2,···,m).則有根樹T有m+1個節(jié)點(diǎn),m條邊,且根據(jù)拉米納超圖構(gòu)造一個有根樹T的時間復(fù)雜度是O(m2).由于有根樹T滿足偏序關(guān)系＜U,?＞,因此有根樹T的構(gòu)造與對應(yīng)的哈斯圖一致[13].有根樹滿足以下定理.

定理2([14])T是一個以e0為根節(jié)點(diǎn)的有根樹,對任意ek∈E,在T中有且僅有一條從e0到ek的有向路,若ei?ek,則在T中有且僅有一條從ek到ei的有向路.

文獻(xiàn)[14]通過構(gòu)造集合覆蓋對應(yīng)的輔助網(wǎng)絡(luò),在輔助網(wǎng)絡(luò)中求解s?t割,利用集合覆蓋和割集的關(guān)系解決集合覆蓋問題.本文在此基礎(chǔ)上,構(gòu)造邊賦權(quán)拉米納超圖對應(yīng)的有根樹求解邊賦權(quán)拉米納超圖最小邊覆蓋問題.

3.2.2 MEC算法和計算復(fù)雜性分析

基于拉米納超圖Hw構(gòu)造對應(yīng)的有根樹T后,現(xiàn)在給出求解邊賦權(quán)拉米納超圖的最小邊覆蓋問題的MEC算法.設(shè)L?{e0,e1,e2,···,em}是T的葉節(jié)點(diǎn)集合,對任意ei∈E,des(ei)表示節(jié)點(diǎn)ei的所有子節(jié)點(diǎn)以及后代節(jié)點(diǎn)的集合,pr(ei)表示節(jié)點(diǎn)ei的唯一父節(jié)點(diǎn).

Algorithm2MEC算法1:構(gòu)造一個關(guān)于拉米納超圖Hw的有根樹T 2:記T的所有葉節(jié)點(diǎn)集合為L,C=?3:if∪ek∈L ek=V then 4:C←L 5:else 6:記M=V? ∪ek∈L ek為缺失元素集合,在T上從e0遍歷包含M中元素的節(jié)點(diǎn)ei,直到對?x∈M,x/∈ei,則C←L?({ei}+des(ei))+{pr(ei)}7:end if 8:從L中的節(jié)點(diǎn)開始從下往上層次遍歷T中節(jié)點(diǎn)直到e0,9:if wei≤ ∑wej then 10:C←C?{ej}+{ei}11:end if 12:輸出C為Hw的最小邊覆蓋.ej∈C∩des(ei)

定理3MEC算法輸出的C為拉米納超圖Hw的最小邊覆蓋.

首先構(gòu)造一個有根樹的時間復(fù)雜度為O(m2),利用MEC算法找邊賦權(quán)拉米納超圖的最小邊覆蓋,算法第2 11步的時間復(fù)雜度是O(m3),即MEC算法時間復(fù)雜度O(m3),所以求解拉米納超圖上最小邊覆蓋問題的時間復(fù)雜度為O(m3).

3.2.3 一個實(shí)例

給定拉米納超圖Hw=(V,E;w),其中V={v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12},E={e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12}.

表1是上述拉米納超圖Hw的超邊權(quán)值表,圖2為Hw的形象化表示,圖3是基于Hw構(gòu)造的有根樹T(U,A;w).運(yùn)用算法2,第1步構(gòu)造實(shí)例對應(yīng)的有根樹T,在第2 7步判斷缺失頂點(diǎn)為v8,刪除e8,得到當(dāng)前邊覆蓋C={e9,e10,e7,e3,e11,e12,e5}?第8 11步,在T中遍歷所有節(jié)點(diǎn),最終得到最小邊覆蓋C={e9,e10,e7,e3,e1},對應(yīng)權(quán)重w={1,2,1,1,4},最小邊覆蓋的權(quán)重和為9.

圖3 拉米納超圖Hw的有根樹T

表1 拉米納超圖Hw邊權(quán)表

圖2 拉米納超圖Hw

4 總結(jié)

求邊賦權(quán)超圖最小邊覆蓋問題是NP難的,但在拉米納超圖上,求解邊賦權(quán)最小邊覆蓋問題是多項(xiàng)式時間可解的.本文首先針對邊賦權(quán)超圖最小邊覆蓋問題設(shè)計了分層算法,通過該算法將超圖分解為一系列導(dǎo)出子圖,根據(jù)每層子圖的構(gòu)造,取每層子圖上的特定集合的并為最小邊覆蓋.設(shè)計的分層算法達(dá)到f近似比,時間復(fù)雜度為O(rm),并給出了該算法的緊例子.其次針對邊賦權(quán)拉米納超圖最小邊覆蓋問題設(shè)計MEC算法,根據(jù)拉米納超圖中邊的關(guān)系構(gòu)造有根樹,然后基于動態(tài)規(guī)劃的思想,按樹的層次遍歷樹中的節(jié)點(diǎn),最后求得邊賦權(quán)拉米納超圖的最小邊覆蓋.MEC算法的時間復(fù)雜度為O(m3).