树上具有惩罚费用的限制性node multicut问题的近似算法

杨惠娟,段江梅,杨子兰

(1.昭通学院数学与统计学院,云南 昭通 657000; 2.丽江文化旅游学校信息学院,云南 丽江 674199)

0 引言

multicut问题是图论与组合优化中非常著名的问题,它具有边和点两种形式,点形式的multicut问题是指:给定赋权图G=(V,E;w)及一个终端点对集合H⊂V×V,其中w:V→R+,求G的一个顶点子集D,使得H中的所有顶点对在G-D中不连通,目标是使得D的权重尽可能小.

限制性node multicut问题是点形式multicut问题的一类子问题,该问题要求所求的顶点子集中不允许有终端点.GUO等[1]研究了完全图、分裂图、区间图上的点multicut 问题,并证明了该问题限制在这三类特殊图上时也是NP难问题.PAPADOPOULOS[2]证明了置换图上的无限制性 node multicut问题是多项式可解的,且设计了时间复杂度为O(n3)的算法,其中n为图的顶点数.

一般的multicut问题是要求所有顶点对被断开,而有些顶点对在断开时可能会出现选取的边的权重很大的情况,这时需要考虑拒绝断开这些顶点对,同时支付部分惩罚费用,这就将multicut问题拓展到了具有惩罚费用问题的层面.LIU等[6]将带线性惩罚推广到带次模惩罚,引入了带次模惩罚的树上的多割问题,并且基于原始对偶方案给出了带次模惩罚的树上的多割问题的一个3-近似算法.HOU等[7]研究了树上具有惩罚费用的k-edge multicut问题,该问题推广了树上边multicut问题,并运用线性规划理论和拉格朗日松弛技巧设计了近似值为(4+ε)的算法,其中ε为任意固定正数.侯鑫[8]研究了树上的k-奖励收集多割问题和树上的P奖励收集多割问题,对于树上k-奖励收集多割问题和树上的P奖励收集多割问题,设计了求解其近似值为(4+ε)的算法,其中ε为任意固定正数.侯晨菲[9]主要研究了与次模函数有关的树上多割问题.这些文献重点研究了不同类型的具有惩罚费用的边multicut 问题,但对于图而言,要分离图上的顶点,可以去掉图上的边,也可以去掉图上的顶点,而这些文献对于具有惩罚费用的点multicut 问题的研究较少.本文提出具有惩罚费用的限制性node multicut问题,为了得到很好的结果,将问题限制在树上进行研究.

1 树上具有惩罚费用的限制性node multicut问题

树上具有惩罚费用的限制性node multicut问题是指:给定顶点赋权树T=(V,E;w)及顶点V的k个顶点对构成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每个终端点对{si,ti}都有一个非负的惩罚费用pi,求T的一个顶点子集D,使得D满足D中不含S中的点且对∀i∈{1,2,…,k},{si,ti}在T[V-D]中不连通,其中T[V-D]表示T的由顶点集V-D导出的子图.目标是使D中顶点的权重之和与在T[V-D]中未断开的顶点对的惩罚费用之和最小.

树上限制性node multicut问题是指:给定顶点赋权的树T=(V,E;w)及顶点V的k个顶点对构成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,求T的一个顶点子集D,使得D满足D中不含S中的点且对∀i∈{1,2,…,k},{si,ti}在T[V-D]中不连通.目标是使D中顶点的权重之和最小.

S中的点称为终端点,若S中的点对{si,ti}的惩罚费用非常大,超过断开此点对所选非终端顶点的权重之和,此时只能断开S中所有点对,则树上具有惩罚费用的限制性node multicut问题化为树上限制性node multicut问题,因此该问题作为树上限制性node multicut问题的推广形式是NP完备的.

下面介绍如何将树上具有惩罚费用的限制性node multicut问题归约到树上限制性node multicut问题,并利用线性规划及对偶理论设计算法进行求解.

任给树上具有惩罚费用的限制性node multicut问题的一个实例I:给定顶点赋权的树T=(V,E;w)及顶点V的k个顶点对构成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每个终端点对{si,ti}都有一个非负惩罚费用pi,求T的一个顶点子集D,使得D满足不含S中的点且对∀i∈{1,2,…,k},{si,ti}在T[V-D]中不连通.目标是使D中顶点的权重之和与在T[V-D]未断开的顶点对的惩罚费用之和最小.

下面证明实例I与实例τ(I)的解是等价的,若D是实例I的解,在T[V-D]中未被断开的顶点对要支付惩罚费用,假设被惩罚的所有顶点对的下标构成的集合为N,即N={i|∃pi∈T[V-D],si,ti∈pi, ∀{si,ti}∈S},其中

与实例I的目标函数值一致.

反之,若D′是实例τ(I)的解,即S′中所有顶点对在T′[V′-D′]中都不连通,令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},则N={i|ti″∈D″},则D是实例I的解,下标在N中的顶点对集合是在T[V-D]中未断开的集合,此时实例I与实例τ(I)的目标函数值一样,因此根据上述描述任给树上具有惩罚费用的限制性node multicut问题的一个实例I都可以转化成树上限制性node multicut问题的一个实例τ(I),它们的解可以相互转换,且目标函数值相同.

下面介绍如何利用线性规划的相关理论知识设计求解实例τ(I)的算法,并将算法求得的解转化为实例I的解,并证明转化回来的解的近似值.

2 原始-对偶算法

用0-1整数规划来描述实例τ(I).

对V′-S′中的每一个顶点引入布尔变量xv,用来表示顶点v是否在集合D′中,若v∉D′,则令xv=0,若v∈D′,则令xv=1.P′i表示在树T′中si到t′i之间的路,因为T′是树,因此si到t′i之间的路是唯一的,此时得到实例τ(I)的0-1整数规划,记为IP.

因为整数规划的求解是NP难的,因此对上述整数规划进行松弛,就得如下的线性规划记为LP.

算法的思想:从原始线性规划的一个不可行解∀v∈V′-S′,xv=0及对偶线性规划的一个平凡可行解fi, ∀i∈{1,2,…,k}开始,在每一次迭代过程中保证对偶线性规划的解的可行性,然后逐步调整原始线性规划的解和对偶线性规划的解,使得原始线性规划的解尽可能满足可行性,而对偶规划的解尽可能满足最优性,直到调整到原始线性规划的解满足可行性.

算法具体步骤如下:

输出:断开顶点对所选的非终端点构成的集合D′

步骤1 令fi=0, ∀i∈{1,2,…,k},D′=∅.

步骤2 任取T′的一个顶点作为根节点,假设为v0.

步骤3 计算V′中每一个顶点的深度,即对∀v∈V′(T′)计算顶点v的深度d(v),d(v)表示v到v0的唯一路上边的数目.

步骤4 将步骤3计算得到的所有顶点的深度d(v)从大到小进行排序,d(vn)≥d(vn-1)≥…≥d(v0).

输出:fi,∀i∈{1,2,…,k}及集合D′.

若v∈D′,令xv=1,否则令xv=0,于是上述算法输出的解xv,∀v∈V′-S′及fi,∀i∈{1,2,…,k}分别为松弛线性规划和对偶规划的可行解,于是得到如下结论:

根据文献[10]的性质5得出上述原始线性规划和对偶线性规划的可行解,满足的互补松弛条件是:

(5)

图1 si0到的路及si到ti的路

将上述算法求得的实例τ(I)的解D′,转化成实例I的解,转化方式为:令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},则N={i|ti″∈D″}.于是得到如下定理.

证明

(6)

(7)

(8)

(9)

定理5令OPT,O′PT分别是实例I和实例τ(I)的最优解的值,调用原始-对偶算法求解的实例τ(I)的解转化成实例I的解,则所得的解的近似值为2.

证明 算法求得的实例τ(I)的解为D′,转化成实例I的解为D,N,其中,D为断开终端点对所选的非终端点集合,N为在T-D中未断开的顶点对的下标构成的集合,因此实例τ(I)的最优解可以转化成实例I的一个可行解,故O′PT≤OPT,于是,再由定理3和定理4得到:

综上所述,D中顶点的权重之和与在T[V-D]未断开的顶点对的惩罚费用之和小于等于最优解的2倍,因此这样求得的解D,N的近似值为2.

3 结语

本文研究了树上具有惩罚费用的限制性node multicut 问题,将该问题转化成树上限制性node multicut 问题,并利用线性规划和对偶规划的相关理论设计了近似值为2的算法.下一步将重点研究更多特殊图上的具有惩罚费用的限制性node multicut 问题及其各种推广问题.