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

林雯 王嘉寶 陳智斌

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

1 引言

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

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

本文首先針對邊賦權超圖最小邊覆蓋問題采用分層算法設計近似算法,達到f近似比.再對邊賦權拉米納超圖,設計求解最小邊覆蓋問題的精確算法,首先構造對應的有根樹[9],然后利用有根樹的特殊性,基于動態規劃的思想[10],對樹從下往上按層次遍歷各節點[11],求解出邊賦權拉米納超圖上的最小邊覆蓋.

2 邊賦權超圖最小邊覆蓋問題

2.1 問題描述

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

2.2 分層算法

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

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

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

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

證明假設常數c滿足w(e)=c·|e|,C?是超圖Hw的最優邊覆蓋,OPT是C?對應的最優值.由于C?覆蓋Hw的所有頂點,故有

由每個頂點至多在f條邊中,有

進而有

引理1得證.

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

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

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的頂點添加到Pp中4:Hwp+1←Hwp[Ep?(Dp∪Wp)],Hwp+1為Hwp的導出子圖,從Ep中刪除Pp包含的頂點和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分層算法是一個關于邊賦權超圖最小邊覆蓋問題的近似算法,近似比為f.

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

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

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

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

2.3 緊例子

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

圖1 邊賦權完全二部圖Kf,f

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

3 邊賦權拉米納超圖最小邊覆蓋問題

3.1 邊賦權拉米納超圖

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

3.2 邊賦權拉米納超圖最小邊覆蓋算法

3.2.1 構造有根樹

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

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

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

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

關于有根樹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個節點,m條邊,且根據拉米納超圖構造一個有根樹T的時間復雜度是O(m2).由于有根樹T滿足偏序關系＜U,?＞,因此有根樹T的構造與對應的哈斯圖一致[13].有根樹滿足以下定理.

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

文獻[14]通過構造集合覆蓋對應的輔助網絡,在輔助網絡中求解s?t割,利用集合覆蓋和割集的關系解決集合覆蓋問題.本文在此基礎上,構造邊賦權拉米納超圖對應的有根樹求解邊賦權拉米納超圖最小邊覆蓋問題.

3.2.2 MEC算法和計算復雜性分析

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

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

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

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

3.2.3 一個實例

給定拉米納超圖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的超邊權值表,圖2為Hw的形象化表示,圖3是基于Hw構造的有根樹T(U,A;w).運用算法2,第1步構造實例對應的有根樹T,在第2 7步判斷缺失頂點為v8,刪除e8,得到當前邊覆蓋C={e9,e10,e7,e3,e11,e12,e5}?第8 11步,在T中遍歷所有節點,最終得到最小邊覆蓋C={e9,e10,e7,e3,e1},對應權重w={1,2,1,1,4},最小邊覆蓋的權重和為9.

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

表1 拉米納超圖Hw邊權表

圖2 拉米納超圖Hw

4 總結

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