文章快速检索     高级检索
  北京化工大学学报(自然科学版)  2019, Vol. 46 Issue (1): 124-128   DOI: 10.13543/j.bhxbzr.2019.01.019
0

引用本文  

张文杰, 涂建华. Series-Parallel图上最小权顶点覆盖3-路问题的有效算法[J]. 北京化工大学学报(自然科学版), 2019, 46(1): 124-128. DOI: 10.13543/j.bhxbzr.2019.01.019.
ZHANG WenJie, TU JianHua. An efficient algorithm for the minimum weight vertex cover 3-path problem on series-parallel graphs[J]. Journal of Beijing University of Chemical Technology (Natural Science), 2019, 46(1): 124-128. DOI: 10.13543/j.bhxbzr.2019.01.019.

第一作者

张文杰, 男, 1995年生, 硕士生.

通信联系人

涂建华, E-mail:tujh81@163.com

文章历史

收稿日期:2018-05-24
Series-Parallel图上最小权顶点覆盖3-路问题的有效算法
张文杰 , 涂建华     
北京化工大学 理学院, 北京 100029
摘要:研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O(|V|)。
关键词Series-Parallel图    顶点覆盖k-路问题    有效算法    动态规划    
An efficient algorithm for the minimum weight vertex cover 3-path problem on Series-Parallel graphs
ZHANG WenJie , TU JianHua     
Faculty of Science, Beijing University of Chemical Technology, Beijing 100029, China
Abstract: Given a vertex-weighted graph G=(V, E) and a positive integer k ≥ 2, the minimum weight vertex cover k-path problem (MWVCPk) asks for a vertex subset FV with minimum weight such that every path of order k contains at least one vertex from F. For any integer k ≥ 2, MWVCPk on general graphs is NP-hard. In this paper, we study MWVCP3 on Series-Parallel graphs and present a dynamic programming algorithm with runtime O(|V|).
Key words: Series-Parallel graphs    vertex cover k-path problem    efficient algorithms    dynamic programming    
引言

给定一个无向图G=(V, E)和正整数k≥2,顶点覆盖k-路问题(MVCPk)要求找到图G的一个最小顶点子集F,使得图G中的任何一条k-路都至少有一个顶点在F中,其中k-路指包含k个顶点的路。一个集合如果为MVCPk的可行解,则称该集合为顶点覆盖k-路集合(VCPk集)。定义顶点覆盖k-路数为一个最小VCPk集包含的顶点数,不难看出,k=2时的MVCPk正是著名的“顶点覆盖问题”,因此,MVCPk是顶点覆盖问题的一个自然推广。同时,MVCPk也属于一类顶点删除问题,它可以被定义为:给定一个无向图G和一个正整数k≥2,寻找权重和最小的顶点子集FV,使得将F从图G中删除后剩余子图不包含k-路。点覆盖k-路问题的提出源于两个实际问题,即无线传感器网络加密[1]和交通摄像头安装[2]问题。

最小权顶点覆盖k-路问题(MWVCPk)是MVCPk的赋权版本,即给定的图为顶点赋权图,此时要求找到一个权重和最小的VCPk集。对于任意的k≥2,MVCPk都是NP难的[2],因此研究者们主要从近似算法和特殊图上的有效算法两个角度去研究此问题。近似算法方面,Kardoš等[3]给出了MVCP3问题一个近似度为23/11的随机近似算法;Tu等[2]考虑了MWVCP3,并给出了一个2-近似算法。在特殊图上的有效算法方面,Brešar等[4]给出了路图、圈图以及树图上MWVCPk的有效算法;Tu等[5-6]对于三正则图的MVCP3和MVCP4分别给出了1.57-近似算法与2-近似算法;Devi等[7]对二部图、d-正则图和K1, 4-free图上的MVCP4进行了研究,分别给出了近似度为2、2和3的近似算法。实际生活和工程中所遇到的某些问题,通常可以简化到某一类特殊性质的图上,当处理特殊图上的MWVCPk问题时,往往会比一般图处理起来更快、更精确,这表明解决特殊图上的MWVCPk问题是有意义的。

Series-Parallel(SP)图是一类特殊图,由Duffin[8]在研究串、并联电路网络时提出,它在电路网络设计、基因编码排序等领域有着广泛应用。Nagy等[9]对SP的顶点覆盖问题进行了研究,得到一个实时并行算法。MVCPk作为顶点覆盖问题的推广,在k>2时,对SP图还没有一个精确的算法。因此,本文考虑了SP图上的MWVCP3,利用动态规划方法给出了一个有效算法,算法的运行时间为O(|V|)。

1 相关定义

定义1  一个Series-Parallel(SP)图可以递归定义如下。

1) 一条边(s, t)是一个起点为s、终点为t的SP图。

2) 设G1G2是两个SP图,s1, t1s2, t2分别是它们的起点和终点,由G1G2通过串联或并联构造的新图G仍然是一个SP图,其中G的起点和终点分别为s, t。串联是将图G1的终点t1G2的起点s2粘合,将s1t2作为新图G的起点和终点;并联是将图G1的起点s1G2的起点s2粘合作为新图G的起点s,将图G1的终点t1G2的终点t2粘合作为新图G的终点t。串联与并联构造图G图 1所示。

图 1 串联与并联示例 Fig.1 Example of a series and parallel connection

3) 有限次地应用步骤2)中串联、并联规则构造出的新图G即是SP图。

定义2  设G=(V, E)是SP图,它的起点和终点分别为st;设G′=(V′, E′)是图G的子图,如果存在G′的两个顶点s′和t′满足条件①、②,则G′称为起点是s′、终点是t′的p-图。

G′是SP图, 它的起点和终点分别为s′和t′。

② 对于顶点s′,满足s′=s,或者满足存在一条边(x, y)∈EE′,其中xV′并且y=s′∈V′;对于顶点t′, 满足t′=t或者满足存在一条边(z, w)∈EE′,其中zV′并且w=t′∈V′。此外,对于任意的顶点u, v,都有(u, v)∉E,其中uV′且us′, t′,vVV′且vs, t

定义3  设图G′=(V′, E′)是SP图Gp-图,它的起点和终点分别为st;设FG′的VCP3集,将v∈{s, t}标记为vα, α∈{1, 00, 01},v1表示状态vFv00表示状态vF, dG′-F(v)=0,v01表示vF, dG′-F(v)=1。

根据定义3,给定一个p-图G,以及它的任意一个VCP3F,那么该p-图G的起点和终点st各自的状态为{s1, s00, s01}和{t1, t00, t01}。不同状态的起点和终点通过组合后可能的状态有9种:{(s1, t1), (s1, t00), (s1, t01), (s00, t1), (s00, t00), (s00, t01), (s01, t1), (s01, t00), (s01, t01)}。每种状态下对应的VCP3集记为F(sα, tβ),其中,α, β∈{1, 00, 01}。

定义4  设图G′=(V′, E′)是SP图Gp-图,它的起点和终点为st,则G′的所有F(sα, tβ)构成的集合为$\mathscr{F}$ (sα, tβ)。记$\mathscr{F}$ (sα, tβ)中权重最小的VCP3集为S(sα, tβ),记S(sα, tβ)中所有顶点的权值和为W(sα, tβ)。当$\mathscr{F}$ (sα, tβ)为空集时,对应的W(sα, tβ)规定为+∞。

注意,$\mathscr{F}$ (sα, tβ)为空集代表不存在满足状态(sα, tβ)的顶点覆盖3-路集合,而S(sα, tβ)为空集代表空集本身即为一个满足状态(sα, tβ)的顶点覆盖3-路集合。

每个SP图G都关联着一棵树T(G),这棵树表明了G是如何通过最初的基本图递归地构成。树T(G)是一棵二叉树,其中叶子节点表示构成SP图的基本图,内部节点表示串联或并联连接。为了更好地描述算法,对T(G)给出如下更精确定义,并对其标记。

定义5  设G=(V, E)是SP图, 它的起点和终点分别为s, tT(G)=(VT, ET)是一颗每个内部节点有两个子节点和|E|个叶子的根树。

T的节点用如下方法标记:①树T(G)的根节点标为(s, t);②对于任意边(u, v)∈E,在T(G)中都存在一个标记为(u, v)的叶子;③对于内部标记为(x, y)形式的节点uVT,将以u为父节点的左子树和右子树的根节点分别标记为(x, y)、(x, y)或者(x, z)、(z, y)的形式,其中zV;④若作前一种标记,则称u为P型节点;若作后一种标记,则称u为S型节点,称T(G)为G的分析树。

例如,根据定义5对图 2(a)所示的图G对应的二叉分析树进行了标记,标记结果如图 2(b)所示。

图 2 SP图G及其分析树结构 Fig.2 SP graph G and its parse tree structure

但是一个SP图的分析树并不是唯一的,本文所提出的算法并不要求分析树是唯一的。

2 SP图上MWVCPk的动态规划算法 2.1 算法主步骤

T为SP图G的一颗分析树,对于树的任一节点u,记T(u)为Tu及其所有子孙节点导出的子树;记Tl(u)和Tr(u)分别为u的左、右子节点及其各自所有子孙节点导出的子树。记MWVCPk最优解的权值之和为Wk(G),通过算法1将得到SP图GW3(G)。算法1步骤如下。

算法1   SP图的MVCP3问题

输入 一个SP图G=(V, E),它的起点和终点分别为s, t

1) 构建分析树T(参见2.2节);

2) 计算初始时每个叶子节点的S(sα, tβ),及S(sα, tβ)中顶点的权值和(参见2.3节);

3) 自底向上遍历T, 对于T的每个内部节点u, 计算T(u)的S(sα, tβ),及S(sα, tβ)中顶点的权值和(参见2.4节);

4) 在图G的最终状态集S(sα, tβ)找到问题的最优解,并计算出相应的权值W3(G)(参见2.5节);

输出 最小权顶点覆盖3-路问题的最优解及其权值和。

2.2 构建二叉分析树 2.2.1 串联、并联分解规则

输入为一个SP图G=(V, E), 并且其起点和终点分别为st;输出为图G的一棵分析树T。给定一个SP图G=(V, E)。本文提出一种线性时间算法来构建二叉分析树。

如果SP图G由两个p-图G1G2通过串联构成,则用串联分解规则生成分析树T,将G对应的子树的根节点标记为(s, t),将左右子树Tl(G1)、Tr(G2)的根节点分别标记为(s, x)、(x, t),其中sx为图G1的起点和终点,xt为图G2的起点和终点。

如果SP图G由两个p-图G1G2通过并联构成,则用并联分解规则生成分析树T, 并将G对应的子树的根节点标记为(s, t),将左、右子树Tl(G1)、Tr(G2)的根节点分别标记为(s, t)、(s, t),其中s, t为图G1G2的起点与终点。串联分解和并联分解示意图如图 3所示。

图 3 串联分解和并联分解示意图 Fig.3 Schematic diagram of series decomposition and parallel decomposition
2.2.2 二叉分析树的构建

G=(V, E)的端点为s, t,令Φ=V, 利用算法2构建图G的二叉分析树。

算法2  构建二叉树

1) 从Φ中选顶点v

2) 处理以v为起点的边,如果发现边(v, w)的重数大于等于2,则运用并联分解规则直到顶点v的度等于1;

3) 如果只有一条边(u, v)以v为终点并且仅有一条边(v, w)以v为始点,应用串联分解规则,以新边(u, w)代替边(u, v)和(v, w),如果u不在Φ中则将u加入Φ中,如果w不在Φ中则将w加入Φ中;

4) 从Φ中删掉v,如果Φ={s, t}并且边(s, t)之间没有重边,转至步骤5),否则转至步骤1);

5) 返回图G的二叉分析树。

2.3 初始状态集构建

输入为分析树T的叶子节点(u, v),输出为叶子对应的状态集。对于整棵分析树, 在初始时刻它的每个叶子节点标记代表原图中的一条边(K2)。边的两个端点在所有可能状态下的相应权值的最小状态集分别为:S(u1, v1)={u, v}, S(u1, v00)={u}, S(u00, v1)={v}, S(u01, v01)=Φ。其余状态下$\mathscr{F}$ (sα, tβ)为空集。这些状态集对应的权值和W(sα, tβ)为:WK2(u1, v1)=w(u)+w(v), WK2(u1, v00)=w(u), WK2(u1, v01)=+∞, WK2(u00, v1)=w(v), WK2(u00, v00)=+∞, WK2(u00, v01)=+∞, WK2(u01, v1)=+∞, WK2(u01, v00)=+∞, WK2(u01, v01)=0。

2.4 内部节点递归处理 2.4.1 串联情形

输入为一个内部节点u及其左子树Tl(u)和右子树Tr(u)的状态集,如果内部节点u被标记为(x, y),则u的左右子树的根被标记为(x, z)和(z, y),其中zV;输出为子树T(u)的所有状态集S(xα, yβ)。

S1(xα, zβ)和S2(zα, yβ)分别是与左子树和右子树对应的子图的状态集,其中,α, β∈{1, 00, 01},则:

$ S({x^\alpha }, {y^\beta }) = \mathop {{\rm{argmin}}}\limits_{权值最小} \left\{ \begin{array}{l} {S_1}({x^\alpha }, {z^1}) \cup {S_2}({z^1}, {y^\beta }), \\ {S_1}({x^\alpha }, {z^{{0_1}}}) \cup {S_2}({z^{{0_0}}}, {y^\beta }), \\ {S_1}({x^\alpha }, {z^{{0_0}}}) \cup {S_2}({z^{{0_1}}}, {y^\beta }), \\ {\rm{ }}{S_1}({x^\alpha }, {z^{{0_0}}}) \cup {S_2}({z^{{0_0}}}, {y^\beta }) \end{array} \right\} $

因此,记G中与T(u)对应的子图为GT(u),其MWVCP3集合的权重为W3(GT(u))=$\underset{\alpha, \beta }{\mathop{\text{min}}}\, \{W(S({{x}^{\alpha }}, {{y}^{\beta }}))\}$,对应的最优解集合是$\underset{\alpha, \beta }{\mathop{\text{arg }\!\!~\!\!\text{ min}}}\, \{W(S({{x}^{\alpha }}, {{y}^{\beta }}))\}$

2.4.2 并联情形

输入为一个内部节点u及其左子树Tl(u)和右子树Tr(u)的状态集,如果内部节点u被标记为(x, y), 则u的两个子节点都被标记为(x, y);输出为子树T(u)的所有状态集S(xα, yβ)。

S1(xα, yβ)和S2(xα, yβ)分别是与左子树和右子树对应的子图的状态集,其中α, β∈{1, 00, 01},则有

$ \begin{array}{l} S({x^1}, {y^1}) = {S_1}({x^1}, {y^1}) \cup {S_2}({x^1}, {y^1})\\ S({x^1}, {y^{{0_1}}}) = \mathop {{\rm{argmin}}}\limits_{权值最小} \left\{ \begin{array}{l} {S_1}({x^1}, {y^{{0_1}}}) \cup {S_2}({x^1}, {y^{{0_0}}}), \\ {S_1}({x^1}, {y^{{0_0}}}) \cup {S_2}({x^1}, {y^{{0_1}}}) \end{array} \right\} \end{array} $
$ \begin{array}{l} S({x^1}, {y^{{0_0}}}) = {S_1}({x^1}, {y^{{0_0}}}) \cup {S_2}({x^1}, {y^{{0_0}}})\\ S({x^{{0_1}}}, {y^1}) = \mathop {{\rm{argmin}}}\limits_{权值最小} \left\{ \begin{array}{l} {S_1}({x^{{0_1}}}, {y^1}) \cup {S_2}({x^{{0_0}}}, {y^1}), \\ {S_1}({x^{{0_0}}}, {y^1}) \cup {S_2}({x^{{0_1}}}, {y^1}) \end{array} \right\} \end{array} $
$ \begin{array}{l} \;\;\;S({x^{{0_1}}}, {y^{{0_1}}}) = \\ \mathop {{\rm{arg}}\;{\rm{min}}}\limits_{权值最小} \left\{ \begin{array}{l} {S_1}({x^{{0_1}}}, {y^{{0_1}}}) \cup {S_2}({x^{{0_0}}}, {y^{{0_0}}}), {\rm{ }}\\ {S_1}({x^{{0_1}}}, {y^{{0_0}}}) \cup {S_2}({x^{{0_0}}}, {y^{{0_1}}}), \\ {S_1}({x^{{0_0}}}, {y^{{0_1}}}) \cup {S_2}({x^{{0_1}}}, {y^{{0_0}}}), \\ {S_1}({x^{{0_0}}}, {y^{{0_0}}}) \cup {S_2}({x^{{0_1}}}, {y^{{0_1}}}) \end{array} \right\} \end{array} $
$ \begin{array}{l} \;\;\;\;\;S({x^{{0_1}}}, {y^{{0_0}}}) = \\ \mathop {{\rm{arg}}\;{\rm{min}}}\limits_{权值最小} \left\{ \begin{array}{l} {S_1}({x^{{0_1}}}, {y^{{0_0}}}) \cup {S_2}({x^{{0_0}}}, {y^{{0_0}}}),\\ {S_1}({x^{{0_0}}}, {y^{{0_0}}}) \cup {S_2}({x^{{0_1}}}, {y^{{0_0}}}) \end{array} \right\} \end{array} $
$ S({x^{{0_0}}}, {y^1}) = {S_1}({x^{{0_0}}}, {y^1}) \cup {S_2}({x^{{0_0}}}, {y^1}) $
$ \begin{array}{l} {\rm{ }}S({x^{{0_0}}}, {y^{{0_1}}}) = \\ \mathop {{\rm{arg}}\;{\rm{min}}}\limits_{权值最小} \left\{ \begin{array}{l} {S_1}({x^{{0_0}}}, {y^{{0_1}}}) \cup {S_2}({x^{{0_0}}}, {y^{{0_0}}}), \\ {S_1}({x^{{0_0}}}, {y^{{0_0}}}) \cup {S_2}({x^{{0_0}}}, {y^{{0_1}}}) \end{array} \right\} \end{array} $
$ S({x^{{0_0}}}, {y^{{0_0}}}) = {S_1}({x^{{0_0}}}, {y^{{0_0}}}) \cup {S_2}({x^{{0_0}}}, {y^{{0_0}}}) $
2.5 根节点

分析树的根节点r对应的图正是G,根节点的标记为(s, t),因此MWVCP3集合的权重为W3(G)= $\underset{\alpha, \beta }{\mathop{\text{min}}}\, \{W(S({{s}^{\alpha }}, {{t}^{\beta }}))\}$,对应的最优解集合为$\underset{\alpha, \beta }{\mathop{\text{arg }\!\!~\!\!\text{ min}}}\, ~\{W(S({{s}^{\alpha }}, {{t}^{\beta }}))\}$

3 算法的时间复杂度分析

定理1  给定顶点赋权的SP图G=(V, E),算法1的时间复杂度为O(|V|)。

证明   因为分析树的每个叶子节点对应SP图的一条边,所以叶子节点的个数为m=|E|。又因为分析树是一棵二叉树,所以树的深度为O(lg m),树的节点数为O(m),因此执行步骤1)(算法中,下同)时构建分析树的时间复杂度为O(m)。执行步骤2)时,要求考察叶子节点的所有状态集,根据2.3节中给出的状态集权值和计算公式W(sα, tβ)很容易看出时间复杂度为O(1)。执行步骤3)时需要自下而上递归分析树,从而得到分析树中每个节点的状态, 在具体考察某一确定的内部节点时,该节点的状态集由两个子节点的状态集计算得到, 计算过程中无论串联或并联情形,得到此内部节点状态集的时间复杂度都是O(1)。算法执行到步骤4)时,只需要从根节点的所有状态集中找出权值和最小的状态,时间复杂度显然为O(1)。综上,算法总的时间复杂度为O(m)。又因SP图为平面图,有O(m)=O(|V|),即算法1的时间复杂度为O(|V|)。定理1得证。

4 结束语

本文针对SP图进行了研究,利用动态规划的思想,给出了SP图上最小权顶点覆盖3-路问题的有效算法。沿着这个思路,可以考虑其他特殊图上的顶点覆盖k-路问题,并给出相应的近似算法或有效算法。

参考文献
[1]
NOVOTNY M. Design and analysis of a generalized canvas protocol[C]//WISTP 2010: Security and Privacy of Pervasive Systems and Smart Devices. Passau, 2010: 106-121.
[2]
TU J H, ZHOU W L. A primal-dual approximation algorithm for the vertex cover P3 problem[J]. Theoretical Computer Science, 2011, 412(50): 7044-7048. DOI:10.1016/j.tcs.2011.09.013
[3]
KARDOŠ F, KATRENIC J, SCHIERMEYER I. On computing the minimum 3-path vertex cover and dissociation number of graphs[J]. Theoretical Computer Science, 2011, 412(50): 7009-7017. DOI:10.1016/j.tcs.2011.09.009
[4]
BREŠAR B, KRIVOŠ-BELLUŠ R, SEMANIŠIN G, et al. On the weighted k-path vertex cover problem[J]. Discrete Applied Mathematics, 2014, 177: 14-18. DOI:10.1016/j.dam.2014.05.042
[5]
TU J H, YANG F M. The vertex cover P3 problem in cubic graphs[J]. Information Processing Letters, 2013, 113: 481-485. DOI:10.1016/j.ipl.2013.04.002
[6]
LI Y C, TU J H. A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs[J]. International Journal of Applied Mathematics and Computer Science, 2014, 91(10): 2103-2108.
[7]
DEVI N S, MANE A C, MISHRA S. Computational complexity of minimum P4 vertex cover problem for regular and K1, 4-free graphs[J]. Discrete Applied Mathematics, 2015, 184: 114-121. DOI:10.1016/j.dam.2014.10.033
[8]
DUFFIN R J. Topology of series-parallel networks[J]. Journal of Mathematical Analysis and Applications, 1965, 10(2): 303-318. DOI:10.1016/0022-247X(65)90125-3
[9]
NAGY M, AKL S G. Real-time minimum vertex cover for two-terminal Series-Parallel graphs[J]. International Journal of High Performance Computing & Networking, 2000, 4(5): 347-356.