树上的限制性node multicut问题

杨惠娟

（昭通学院数学与统计学院，云南昭通 657000）

1 背景知识

1.1 问题的现实意义割集理论在图论和组合优化中占有举足轻重的地位，它不仅可以用来设计精确算法，同时还被用来设计一些问题的近似算法。而且它在现实中的应用也是非常广泛的，特别是在城市建设、道路规划等方面。原始的最小割集问题是指给定一个连通的边赋权图G 以及在G 中指定两个点s,t。目标是找G 的一个最小权重的边子集D 使得s,t 在G-D 中不连通。对于这个问题可以用图论中的经典算法最大流算法〔1-2〕多项式求解并且得到了最大流最小割集定理。但是随着对问题的不断深入割集问题已经产生了很多复杂的推广问题，不同领域的研究者已经对这些问题做了研究并得到了一些相应的成果。

1.2 Multicut 问题的研究现状Multicut 问题分为edge multicut问题和node multicut问题。

edge multicut 问题：是指给定一个连通边赋权图G=(V,E;w)以及由G 中顶点构成的k 个顶点对集合S，即 S={(s1,t1),(s2,t2),…，(sk,tk)}，D 是 G 的一个边子集，如果S 中的每一个顶点对在G-D 中不连通，则称D 为G 的edge multicut。目标是求G 的最小权重的edge multicut D ，即

node multicut 问题：是指给定一个连通边赋权图G=(V,E;w)以及由G 中顶点构成的k 个顶点对集合S，即 S={(s1,t1),(s2,t2),…,(sk,tk)}，G 的一个顶点子集D，如果D 满足S 中的每一个顶点对在G-D 中不连通，则称D 为G 的node multicut。目标是求G 的最小权重的 node multicut D，即

如果去掉的顶点集合D 中允许有S 中的点则称node multicut为无限制node multicut问题，如果去掉的顶点集合D 中不允许有S 中的点则称node multicut 问题为限制性node multicut 问题。无限制node multicut问题可以多项式的归约到限制性node multicut问题，因为任给无限制node multicut 问题的一个实例I ，对实例I 中每一个顶点对(si,ti)构造一个新的顶点对及两条新的边，然后将新的k 个顶点对构成的集合作为限制性node multicut 问题中考虑的k 个顶点对。通过这种变换就得到了限制性node multicut问题的一个实例。

根据所给的连通赋权图G 是有向的或是无向的，multicut 问题也有4 种形式分别为：有向图的edge multicut 问题〔3-4〕，无向图的 edge multicut 问题，有向图的node multicut 问题，无向图的node multicut 问题。

当k=1 时，edge multicut 问题一样都是割集问题，所以可以利用最大流算法求解。

当 k=2 时，Hu〔5〕中说明了上述4种形式的multicut问题是多项式可解的。

当 k ≥3 时，Dahlhaus 等在文献〔6〕中证明了一般图上的edge multicut 问题是NP 完备的并且不能得到一个PTAS，除非P=NP，同时他给出了一个近似值为 O(log k)的算法。Chawla 和 Krauthgamer〔7〕证明了要想得到这个问题的一个常数近似算法是NP难的并且提出猜想: 这个问题是Ω(log log ||V )不可近似的。对于一般图上的node multicut 问题，Garg和Vazirani〔8〕给出了一个近似值为O(log k)的算法。

一般图上multicut 问题的求解是非常难的，很多研究者将它限制在特殊图上进行研究，得到了一些很好的成果。树上的edge multicut 问题，Garg 和Vazirani〔9〕通过最小点覆盖问题归约到此问题，从而说明它是NP 完备，并且设计了近似值为2 的算法。Costa 等〔10〕给出了一个贪婪算法在多项式时间内找到了根树上的edge multicut 问题的最优解。Calinescu 等〔11〕主要研究了无赋权且满足度限制和树宽度限制的图上的node multicut问题并做出了如下成果：

（1）在树宽度至多为2 的图上无限制的node multicut 问题是NP 难的并且当图满足树宽度限制时，无限制的node multicut问题存在PTAS。

（2）证明了有向edge multicut 问题在满足树宽度是1和图的最大出度与入度都为3的有向图中是NP 难的。

（3）树上当顶点的权重是1 时无限制的node multicut问题是多项式可解的。

Guo 和Huffner 等在文献〔9〕中证明了区间图上的无限制性node multicut 是 NP 难的，限制性的node multicut 是多项式可解的。Papadopulos〔12〕研究了置换图上的限制性node multicut问题并且给出了一个多项式时间算法。

对于树上的 k-edge multicut 问题 Mestre〔13〕设计了一个近似值为2+ε 的近似算法，树上推广的kedge multicut 问题文献〔14〕中设计了一个近似值为O(q)的近似算法。

2 树上的限制性node multicut问题

定义1任给一个连通边赋权树T=(V,E;w)以及由T 中顶点构成的k 个顶点对集合S，即S={(s1,t1),(s2,t2),…,(sk,tk)}，其中 w:V-S → R+，目标是求 G 的一个顶点子集D，并且D 满足如下条件：

（1）D 中不含 S 中的点；

（2）S 中的每一个顶点对在T-D 中不连通；

首先说明这个问题是NP 完备的。方法是通过树上的edge multicut问题归约到此问题。任给树上的edge multicut问题的实例I：T=(V,E;w)，S={(s1,t1),(s2,t2),…,(sk,tk)}，其中 w:E →R+，目标是求 T 的一个权重最小的边子集 D ，即，使得 S中的每一个顶点对在T-D 中不连通，其中D 称为T 的edge multicut。构造树上的限制性node multicut 问题的一个实例τ(I)，构造方法：在T 的每一条边上插入一个点，这个新插入的点的权重为它所在这条边的权重，而原图T 中不在S 中的点的权重为无穷大的数（至少是T 中所有边的权重之和的c(c ＞1)倍），这样得到的就是树上的限制性node multicut 问题的一个实例。如果有一个算法A 能够解决τ(I)那么它也能解决实例I 。因为通过算法A 求得的τ(I)的解D 中是不可能含有原图T 中的任何一个顶点，它只能含有新构造的点，所以D 中这些点对应到原图T 中边的集合就是实例I 的解。因此树上的限制性node multicut问题是NP 完备的。

下面用线性规划来描述树上的限制性node multicut问题。

令D 表示此问题的限制性node multicut，dv表示顶点v 是否属于D，如果v 属于D 则dv=1，否则dv=0。因为树上的任意两个点之间只有唯一的一条路，所以S 中的每一顶点对si到ti(i=1,2,3,…,k)的唯一的路用Pi来表示。则原始线性规划如下：

它的松弛线性规划用RLP：

对S 中的每一顶点对(si,ti)对应的路Pi引进一个变量 fi，fi可以理解为分配在Pi上的一个多物种流，则RLP 的对偶线性规划为如下的DRLP：

则松弛以后的互补松弛条件如下：

原始互补松弛条件：对每一个v ∈V-S,dv≠0，则

松弛以后的对偶互补松弛条件：对每一个i ∈{1,2,3,…,k}，fi≠ 0，则

算法思想是：先找一个满足原始松弛条件的可行解，然后在保证每一步都是可行解的条件下，一步步的调整这个解，使得它逐步向松弛以后的对偶互补松弛条件靠近，最终满足松弛的对偶互补松弛条件。具体算法如下。

输入：T=(V,E;w)以及由T 中顶点构成的k 个顶点对集合 S ，即 S={(s1,t1),(s2,t2),…,(sk,tk)} ，其中w:V-S → R+；

输出：限制性的node multicut D和{f1,f2,f3,…,fk}。

Begin

步骤1：令 f1=f2=f3=…=fk=0，D=φ；

步骤2：对S 中的每一个顶点对(si,ti)考虑si到ti的路Pi，检查Pi上的点是否全是S 中的点，如果是则输出：此问题无可行解，否则转步骤3；

步骤3：因为树T 是无向的，所以可以任取一点作为树的根结点，假设这个点为v0，对T 中的每一个顶点v 计算depth(v)，depth(v)表示的是点v 到根结点v0的路P 上的边的数目；

步骤4：将步骤3 计算得到的depth(v)按从大到小的顺序进行排序记为：depth(v1)≥depth(v2)≥depth(v3)≥… ≥depth(vm)；

步骤5：按步骤4的顺序考虑每一个顶点vi，假设已经考虑完前面k 个点，则下一步考虑vk+1，当考虑到vk+1时，先找出S 中所有使得lca(si,ti)=vk+1的顶点对(si,ti)，其中lca(si,ti)表示的是一个点它满足这样的性质即它是si到根节点v0的路与ti到根节点v0的路的第一个交点。在每一个顶点对对应的路Pi上最大限度的分配流量，分配的方法如下：

把Pi上的所有饱和点即满足的点按任意的顺序放入D，直到使S 中满足lca(si,ti)=vk+1的所有顶点对对应的Pi上都最大限度的分配到流量为止，此时标记vk+1为已经处理的点，一直重复上述过程直到所有的点都考虑完为止，此时得到

步骤6：假设步骤5 得到的node multicut D=去掉D 中多余的点：方法是从最后一点 v′l开始，考虑 D-{v′l} 是否是T 的node multicut，即S 中的每一个顶点对在(T-D-{v′l})中不连通，则 D:=D-{v′l}，否则继续考虑下一个点直到D中所有的点都考虑完为止；

步骤7：输出{f1,f2,f3,…,fk}和D。

End

算法正确性分析：在算法步骤5 保证了每一个顶点对(si,ti)的路Pi上至少有一个点被饱和也就是每一条路Pi上至少有一个点被选进D 中，所以步骤5 结束得到的D 是node multicut。步骤6 是在保证 D 是node multicut 的条件下去掉 D 中多余的点。因此整个算法结束就得到D 是node multicut。

算法的时间复杂度分析：在步骤4 涉及到的排序用二分法来实现时间复杂度为O(n log n)。在步骤5 中对每一个顶点都考虑至多有n 个顶点，而每个顶点要考虑它的顶点对至多有k 个顶点对，这一步的时间复杂度为O(nk)，所以总的时间复杂度为O(max{kn,n log n})。

定理1 令si,ti是一对有非零流量的顶点对（ fi≠ 0）且 lca(si,ti)=vi是 node multicut，设 si到vi的路为 Pi1，ti到vi的路为 Pi2则有：

证明：假设 |D ⋂V(Pi1) |=2，即算法结束后得到的D 中有 Pi1上的两个点，分别设为 v 和 u ，且depth(v)≥depth(u)。假设算法在步骤5中先考虑的是点v（同理也可以假设考虑的点是u）v 在D。当考虑到u时因为u 在步骤5 时没有被删除，所以在S 中必须有一个顶点对(sj,tj) 使得u 是 Pj在 D 中的点且lca(sj,tj) =depth(vj) 且 depth(vj)≥depth(u)。 在考虑 vj时如果u 在这时被选入D，那么考虑到vi时Pi上已经有饱和点u，此时分配在Pi上的流量为0，这与 Pi是流量路矛盾。如果在此时u 未被选入D 那么在Pj中一定有另外的点u0被选入，在这种情况下算法步骤6 首先考虑的是u，则此时u一定会从D中被删除，这就产生矛盾。

从上面的分析可知，算法得到的解{f1,f2,f3,…,fk}和D 分别是RLP 和DRLP 的可行解，且满足松弛以后的互补松弛条件，因此算法得到的近似值为2。下面我们进一步说明算法得到的解是RLP 和DRLP 的最优解，且具有半整数的性质。因为任何一条流量路上至多只有两个点在D 中，设Pi和Pj是两条流量路且u,v 是Pi在D 中的两个点，u′是Pj在 D 中的唯一的点，那么一定有 u ≠u′且 v ≠u′。否则假设有u=u′或者v=u′在这里只分析u=u′的情况，对于另一种可以同理说明。由算法步骤5 和步骤6 可知无论是选入D 的点还是从D 中删除的点都是按顺序进行操作的，所以当u=u′成立时，我们分为以下两种情况讨论：

（1）在算法步骤5顶点对(sj,tj)先于顶点对(si,ti)被考虑这有两种可能：

如果此时u=u′被选入D，那么当考虑到顶点对(si,ti)时Pi上已经有饱和点u=u′，此时流量的增加值θ 就为0，这与Pi是流量路矛盾。

如果在考虑顶点对(sj,tj)时u=u′未被选入D中，此时一定有Pj上异于u′的点u″被选入 D 中点u′是在考虑后面某一顶点对的时候才被选入，那么算法步骤6先考虑的点是 u′而 D-{u′}是node multicut这与u′是Pj在D 中的唯一点矛盾。

（2）在算法步骤5顶点对(si,ti)先于顶点对(sj,tj)被考虑，此时如果u′被选入则与Pj是流量路矛盾，所以只能是v 被选入。如果不存在另外一个顶点对(sk,tk)使得v 是流量路Pk在D 中的点那么在算法步骤6，v 一定被删除因为D-{v}是node multicut这就产生矛盾。但是即使v 是流量路Pk在D 中的点这也与Pi是流量路或者v 在D 中矛盾。

综上所述：在D 中只有一个点的流量路和在D中有两个点的流量路在D 中的点是不同的。因此可以按如下方式构造RLP 的解对每一条流量路Pi，如果 Pi在 D 中有两个点 u,v 则 du=dv=1/2；如果 Pi在 D 中有一个点u 则du=1，其余除S 中的点外所有点的距离标记为0。这样构造的解一定满足当α=β=1 时的互补松弛条件，所以它是RLP 的最优解且具有半整数的性质。

〔1〕拉文德拉K.阿胡亚，托马斯L.马南提，詹姆斯B.沃琳，等.网络流理论算法与应用〔M〕.北京:机械工业出版社，2005:207-240.

〔2〕刘振宏，蔡茂诚. 组合最优化:计算机算法和复杂性〔M〕.北京:清华大学出版社，1988:248-269.

〔3〕STEFAN K，MARCIN P，MICHAL P.Fixed-parameter tractability of multicut in directed acyclic graphs〔J〕.Computer Science，2012（7391）:581-593.

〔4〕JORGEN B J，ANDERS Y.The complexity of multicut and mixed multicut problems in （di）graphs〔J〕. Theoretical Computer Science，2014（520）:87-96.

〔5〕HU T C.Multicommodity network flows〔J〕.Oper Res，1963（9）:898-900.

〔6〕DAHLHAUS E，JOHNSON D S，PAPADIMITRIOU C H，et al.The complexity of multiterminal cuts〔J〕.SIAM J Comput，1994，23（4）:864-894.

〔7〕CHAWLA S，KRAUTHGAMER R，KUMAR R，et al. On the hardness of approximating multicut and sparsestcut〔J〕.Computational Complexity，2006，15（2）:94-114.

〔8〕GARG N，VAZIRANI V，YANNAKAKIS M. Primal-dual approximation algorithms for integral flow and multicut in trees〔J〕.Algorithmica，1997（18）:3-20.

〔9〕Costa M C，Letocart L，Roupin F. A greedy algorithm for multicut and integral multiflow in rooted trees〔J〕.Operations Research Letters，2003（31）:21-27.

〔10〕CALINESCU G，FERNANDES C G，REED B. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width〔J〕.Journal of Algorithms，2003（48）:333-359.

〔11〕GUO J，HUFFNER F，KENAR E，et al.Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs〔J〕.European Journal of Operational Research，2008（186）:542-553.

〔12〕CHARIS P.Restricted vertex multicut on permutation graphs〔J〕.Discrete Applied Mathematics，2012（160）:1791-1797.

〔13〕 JULIAN M.Lagrangian relaxation and partial cover（extended abstract）〔J〕.Theoretical Aspects of Computer Science，2008（25）:539-550.

〔14〕ZHANG P，ZHU D，LUAN J F.An approximation algorithm for the Generalized k-Multicut problem〔J〕.Discrete Applied Mathematics，2012（160）:1240-1247.