基于搜索树的平面图支配集算法

1、基于搜索树的平面图支配集算法*    摘要:许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W2完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G= (V ,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通

2、过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。关键词:算法;搜索树;支配集;确定参数可解1引言许多来自工业应用的优化问题都是NP难问题。根据NP完全性理论,这些问题很难有多项式时间算法,除非P=NP,正是由于这类问题本身的难解性,人们很长一段时间都是通过设计多项式时间的近似算法去解决此类问题,更多背景知识可参考文献1。确定参数可解(Fixed-Parameter Tractability,简称FPT)作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注,它的起源可以追溯到Graph Minor Theorem

3、定理1。很多NP难问题在给定参数的情况下是可解的(如文献2),这类给定参数可解的问题现在都被归于FPT1,更多的关于使用参数处理问题的思路见文献3。支配集问题是图论中最重要的组合优化问题之一。在FPT的体系下,对一般的图而言支配集问题属于W2-Complete,意味着参数难解,即不可能设计出一个f(k)no(1)复杂度的算法(其中f(k)是任意只依赖k的可计算函数)。即使将此问题限定在平面图的范围中依然属于NP-Complete。本文中,我们考虑在给定的无向平面图G(V, E)中参数化支配集问题,即给出参数k,看是否存在一个大小为k的顶点集合可以支配图中的其他顶点,这个问题属于确定参数可解(F

4、ixed-ParameterTractable)。本文给出基于两组归约规则的搜索树算法以及相关实验。2基本定义和问题描述给定无向平面图G(V, E),V为顶点集合,E为边集合;取顶点uV,则N(u)表示所有与u邻接的点,即N(u)=v|(u ,v )E;支配集即取顶点集合V的一个子集V,对图G中的任意剩余顶点v,都存在某一顶点uV,使得边u, v连接顶点v。所谓平面图即将图嵌入到一个平面中,不存在相交的边。基于参数k的k-支配集问题中,我们设计了一个基于搜索树的算法,将顶点划分成为白色顶点集合W和黑色定点集合B,V=B+W(+表示无公共顶点的并运算)。问题的形式化描述如下:输入:一个黑白图G=

5、(B+W,E)和一个正整数k。参数:k。问题:是否存在至多k个顶点的集合V V,满足对任意顶点uB,存在顶点uNuV或者说是否存在大小为k的顶点集合可以支配所有的黑色顶点。在构建搜索树的过程中,我们将根据度数较小的黑色顶点对搜索树分支扩展。通过对图G的限定,可以保证应用归约后的图中必然存在顶点u,满足deg(u)d。由于没有限定所有顶点度数都小于d,选入支配集的顶点不一定是黑色的。这个形式化的描述直接产生了O(d+1)kn)基于搜索树的支配集算法。3归约规则和搜索树算法在这里使用两组归约法则,从不同的视角对支配集进行处理。两组归约基于同样的原则:通过对图的结构的探索,试图用更简单但不影响问题解

6、答的结构来进行替换。如果对原问题的每个实例(G, k)应用归约后得到实例(G, k),(G, k)存在解当且仅当(G,k)存在解,我们称一组归约规则对某问题sound。第一组归约中,对顶点v的邻接点进行处理。依据节点所具有的不同的邻居结构4,将v的邻居节点分为三个集合N1(v)、N2(v)和N3(v)。如图1a所示。N1(v) :=uN(v) : N(u)N(v)N2(v) :=uN(v)N1(v) : N(u)N1(v)N3(v) :=N(v)(N1(v)N2(v)通过三个子集的定义,可知N1(v)中的顶点不能被N3中的顶点支配。因此,为了控制N3(v)中的顶点,一个好的选择是将顶点v加入支

7、配集。根据归约规则1,这确实是最优选择。规则1对顶点v而言,如果N3(v)不空,那么,从图中移除N2(v)和N3(v)中的顶点,在图G中添加新顶点v以及边v, v。如图1b所示。通过新加入v顶点作为“gadget vertex”,使得在归约后的图中需选择v或者v作为支配集的最优选择4。第二组归约则对某些结构进行简化。在构造搜索树的过程中,将始终从归约过的实例branch-ing。因此,将不断地使用归约对图进行处理。当一个顶点u通过应用某条归约被置入支配集D中,目标参数k减小为k-1且将u的所有邻居置为白色5。图1使用规约法则对支配集v进行处理的结果归约规则如下:(1)删除白色顶点之间的边。(2

8、)删除度为1的白色顶点。(3)如果存在度为1的黑色顶点w,它的邻居为u,则删除w,将u置入支配集,同时将k置为k-1。(4)如果存在度为2的白色顶点u,它有两个黑色邻居为u1和u2由边u1, u2连接,则删除顶点u。(5)如果存在度为2的白色顶点u,它有两个黑色邻居u1和u3,且存在黑色顶点u2使得边u1,u2和 u2, u3存在,则删除顶点u。(6)如果存在度为2的白色顶点u,它有两个黑色邻居u1和u3,且存在白色顶点u2使得边u1,u2和 u2, u3存在,则删除顶点u。(7)如果存在度为3的白色顶点u,它有三个黑色邻居u1、u2和u3,且在图中存在边u1, u2和 u2, u3,则删除顶

9、点u。引理1如果G=(B+W,E)是一个平面图,且已经不能再应用第二组归约规则,那么必然存在一个黑色顶点uB,满足degG(u)7。引理的证明可以参考文献5,主要使用欧拉公式进行了十分复杂的推导。引理保证了应用归约后的图中必然存在某个度为7的顶点,从而保证搜索树算法的复杂度为O(7+1)kn)。算法描述如下:pds-st(B, W, E, k, S):/B是图中黑色顶点的集合/W是图中白色顶点的集合/E是图中边的集合/k是实例的参数/S是当前找到的部分解/预处理对(B, W, k)应用归约规则到无法应用为止;IFk=0 andB=W=then returnS;IFk=0 and (BorW=)

10、 then return;/branching ifk>0选择最小度数的黑色顶点v;B:=BNv;W:=WNv;For eachvBDOE:=u, v|uBW;S:=pds-st(BNv, (WNv,EE, k-1,Sv);IFsTHEN break;OD;IFS=THENFor eachvWDOE:=u, v|uBW;S:=pds-st(BNv, (WNvv, EE, k-1, Sv;IFsTHEN break;OD;ReturnS;4实验4.1实现及测试用例算法使用C+实现,使用了LEDA6作为主要的包来进行开发。应用两组归约规则降低图的复杂度,从而保证构造出有效的搜索树。实验硬件平

11、台使用Pentium4 3.2GHz处理器,2G内存。LEDA构建了组合问题和几何计算的良好的软件平台,提供了相当多的数据类型和算法。它包括了大部分数据类型和算法,如堆栈、队列、链表、集合、字典、有序序列、划分、优先级队列等,以及各种图、点、线段、平面、多边形,以及图论、网络和计算几何中的多个算法。LEDA能支持很多领域的应用6。实验测试用例基于纯组合方法,使用LEDA包中的库函数void random_planar_graph(graph&G, intn,intm)产生。4.2实验结果表1是在不同节点数和不同边密度的图应用两组归约规则后算法得到的结果。可以看出,随着图大小的变化,归约

12、规则的作用变化很大,同时能清楚地观察到在稀疏图中,归约规则的结果更好。将降低算法的效率,因归约所需的额外开销所占比例较大;随着图中边数和顶点数的增大,应用两组归约的算法运行时间明显超过后者。5结束语支配集在电子线路设计、计算机网络以及无线传感器网络等领域存在广泛的应用。本文在FPT体系下应用归约技术得到了此问题的解,对归约规则的作用以及算法运行时间作了比较,展示了基于FPT的算法强大力量。参考文献:1Fellows M R , Langston M A . Nonconstructive Tools forProving Polynomial-Time DecidabilityJ. Journ

13、al of theACM , 1988, 35(3):727-739.2Fellows M R, Langston M A. On Search, Decision and theEfficiency of Polynomial-Time Algorithms J. Journal ofComputer and Systems Sciences, 1994,49(3):769-779.3GDowney R, Fellows M R. Parameterized ComplexityM.Berlin:Springer-Verlag, 1999.4Alber J, Fellows M R, Niedermeier R. Polynomial-Time Da-ta Reduction for Dominating SetJ. Journal of the ACM,2004,51(3):363-384.5Alber J, Fan H, Fellows M R, et al. A Refined Search TreeTechnique for Dominatin