k-元组控制问题的理论计算机科学电子笔记346（2019）

≥可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）401-411www.elsevier.com/locate/entcs具有连续零性质1的图的元组控制M.P. 多布森2号Universidad Nacional de Rosario-阿根廷诉狮子座3罗萨里奥国立大学和CONICET-阿根廷M.I. Lopez Pujato4罗萨里奥国立大学和CONICET-阿根廷摘要k-元组控制问题是指对于一个固定的正整数k，在给定的图中找到一个最小的顶点子集，使得图中的每个顶点至少被这个集合中的k个顶点控制即使对于弦图，k-元组控制问题也是NP-困难的对于圆弧图类，其复杂性对于k2仍然是开放的。一个0， 1-矩阵有连续0由于A. Tucker，其增广邻接矩阵具有列的C0P的图是圆弧。在这篇工作中，我们提供了有效的算法来解决图G上的k-元组控制问题，其增广邻接矩阵对于列具有C 0P，对于每个2 ≤k ≤|U |+3，其中U是G的泛点集.关键词：k-元组控制集，稳定集，邻接矩阵，线性时间第一章符号、定义和符号本文考虑有限简单图G，其中V（G）和E（G）分别表示G的顶点集和边集GJ是G的一个（点）导出子图，记Gj<$G，如果E（ GJ）={uv：uv∈E（G），{u，v}<$VJ}，对某个VJ<$V（G）.必要时，我们用G[VJ]表示GJ。给定SV（G），导出子图1部分由PICT ANPCyT 0410（2017-2020）和1 ING 631（2018-2020）2电子邮件地址：pdobson@fceia.unr.edu.ar3电子邮件地址：valeoni@fceia.unr.edu.ar4电子邮件地址：lpujato@fceia.unr.edu.arhttps://doi.org/10.1016/j.entcs.2019.08.0361571-0661/© 2019由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。402M.P. Dobson等人/理论计算机科学电子笔记346（2019）401G[V（G）\S]记为G−S。为了简单起见，我们写G−v而不是G− {v}，因为v∈V（G）。v∈V（G）的（闭）邻域为NG[v]=NG（v）<${v}，其中NG（v）={u∈V（G）：uv∈E（G）}. G的最小度记为δ（G），它是NG（v）的基数之间的最小值，对所有v∈V（G）.顶点v∈V（G）是泛点，如果NG[v] =V（G）.G中的团是G中两两相邻顶点的子集。G中的稳定集是G中互不相邻顶点的子集，G中最大稳定集的基数记为α（G），称为G的独立（或稳定）数。一个图G是圆弧的，如果它有一个由弧组成的交模型，一个圆，也就是说，如果在G的顶点和圆上的弧族之间存在一一对应，使得当对应的弧相交时，G中的两个不同的顶点相邻。图1示出了所绘制的图G的圆弧模型。一个图G是区间图，如果它有一个由实直线上的区间组成的交模型，也就是说，如果在实直线上存在一个区间族I，并且G的顶点集与I的区间一一对应，使得当对应的区间相交时，G真区间图是具有真区间模型的区间图，即没有区间包含另一区间的交集模型。圆弧图构成了真区间图的一个超类，并且由于它们与“循环”码的关系[ 14 ]和遗传分子的循环排列测试[ 10 ]，它们引起了编码理论工作者的兴趣元素都是1的方阵用J表示，单位图G的方阵M（G），如果顶点v i和v j相邻，则m ij = 1，否则m ij= 0，称之为G的邻接矩阵。注意M（G）是对称的，并且在主对角线上有0。具有m ∈ ij的增广邻接矩阵或邻接矩阵M∈（G）定义为M∈（G）：= M（G）+I，即M（G）在主对角线上加1（见图2，对应于图2的图G）。①的人。一个0， 1-矩阵有连续0这一性质是由Tucker在[14]中提出的。图1显示了一个图G的例子，其增广邻接矩阵（如图2所示）具有此属性。Tucker证明了其增广邻接矩阵具有列C0P的图是圆弧图[14]。Fulkerson和Gross[5]描述了一种有效的算法来测试0， 1-矩阵是否具有列的C 0P，并在存在时获得所需的行置换。对于一个非负整数k，D∈V（G）是G的一个k-元组控制集，如果|≥ k，对任意v ∈ V（G）.| ≥ k, for every v ∈ V (G). 注意G有k-元组控制集，如果M.P. Dobson等人/理论计算机科学电子笔记346（2019）401403v3v6v7v1v4⎜⎜⎟⎟⎜⎟⎛⎜⎞⎟⎜⎜⎝⎟⎟⎠vv3v2v2v5v13v7v4v65Fig. 1. 一个圆弧图G及其圆弧模型。1 1 1 1 0 011 1 1 0 0 011 1 10 1 1 1M（G）=1 0 0 1 1 1 10 0 1 1 1 1 10 0 1 1 1 1 11 11111 1图二. 图1中图G的增广邻接矩阵。且仅当k≤δ（G）+ 1，且G有k-元组控制集D，则|D| ≥k。当k≤δ（G）+ 1时，γ×k（G）表示k-元组控制集的基数且当k > δ（G）+ 1时，γ×k（G γ×k（G）称为G的k-元组控制数[8]。观察γ×1（G）=γ（G），通常的控制数。 另外，对任意图G，γ×0（G）= 0. 当G不连通，则G的k-元组控制数定义为G的连通分支的k-元组控制数之和.因此，在这项工作中，G将总是连通的，并且数k将小于或等于δ（G）+1。对于一个固定的正整数k，k-元组控制问题是在给定的图G中找到G的一个大小为γ×k（G）的k-元组控制集对图G，给定一个正整数t和S∈V（G），其中t≤|S|如果S是G的t-控制集，则称S t -控制G.关于计算复杂度结果，与此概念相关的决策问题（固定k）即使对于弦图也是NP完全的[11]。对任意k的有效算法只对强弦图[11]和P4-整齐图[4]是已知的.这是自然的和具有挑战性的，然后试图找到其他图形类，这些问题是对于圆弧图，文献[1]和[9]中只对k= 1的问题给出了有效的此外，在已知的多项式时间可解的情况下，k= 2的问题，正常区间图构成弦图的最大子类已经研究[13]。适当v404M.P. Dobson等人/理论计算机科学电子笔记346（2019）401Roberts[12]将区间图描述为那些其增广邻接矩阵对于列具有连续1属性的图（也由Tucker [ 14 ]以与利用不同的方法，最近提供了多项式算法用于控制的一些变化，例如适当区间图的k-控制和全k-控制（对于固定的k）[2]。k-支配、k-元组支配和全k-支配问题的细微差别使得它们在各种应用中非常有用，例如在形成代表集或在分布式计算系统中的资源分配中。然而，这些问题都是NP难的，也很难近似[3]。本文研究了增广邻接矩阵具有列C 0 P的圆弧图子类的2-和3-元组控制问题。我们的结果然后允许解决在这个图类的k -元组控制问题，2 ≤k≤|U| +3，其中U是输入图的通用顶点的集合，如果有的话。在第二节和第三节中，我们给出了具有泛顶点的图的k-元组控制的一些性质，对任意正整数k。问题的研究k = 2和k = 3时，算法的运行时间分析和一般情况下的进一步研究在第4节中进行。泛顶点图的2k-元组控制集由定义可知，对任意图G和正整数k，γ×k（G）≥k.此外，对于任何SV（G），值得注意的是，它|S|- 支配G当且仅当S的每个顶点都是泛点。因此，我们可以陈述如下。引理2.1设G是一个图，U是它的泛点集，k是一个正整数。则γ×k（G）= k当且仅当|U| ≥ k。当u是图G的泛顶点，且D∈V（G）k-控制G且u∈/D时，通过将u与D的任意一个顶点挂在一起，得到了另一个包含u的k-元组控制集.从形式上讲，注2.2若G是一个图，u是G的泛顶点，则存在G的一个k-元组控制集D，使得u∈D。从上面的评论，很容易证明以下关系：引理2.3设G是一个图，u是G的泛点，k是正整数.然后γ×k（G）= γ×（k−1）（G− u）+ 1。证据设D是G的k-元组控制集，|D|= γ×k（G）.如果u∈D，则D-u是G-u的（k-1）-元组控制集，因此γ×（k-1）（G-u）+1≤|D|=γ×k（G）.如果u∈/D，由注2.2我们可以构造一个k-元组M.P. Dobson等人/理论计算机科学电子笔记346（2019）401405JG的控制集DJ，|DJ|= γ×k（G）且u∈ Dj，并如上进行，D而不是D。另一方面，设D是G−u的最小（k−1）-元组控制集。很明显，由于u是G的泛顶点，D∈ {u}是G的k-元组控制集.则γ×k（G）≤|D{u}|为|D| +1 = γ×（k−1）（G−u）+ 1，证明是完整的。Q上述引理可以推广如下：命题2.4设G是一个图，U是它的泛点集，k是一个正整数，|U| ≤k− 1。然后γ×k（G）= γ×（k−|U|）（G − U）+|U|.从引理2.1和命题2.4可以清楚地得出以下推论。推论2.5LetG是一个图，U是它的泛顶点的集合，其中Uf=0。如果γ×i（G−U）可以在多项式时间内找到，i = 1，2，3，那么γ×k（G）可以在多项式时间内找到，对于每个k，1 ≤k≤|U|+3。3C0P图。 常规属性回想一下，一个0，1矩阵的列具有C0P，如果它的行有一个排列，在每一列中连续放置0。我们引入以下定义：定义3.1一个图G，其增广邻接矩阵M（G）的列具有C 0 P，称为C 0 P-图。注3.2若G是C 0 P-图，则G-U是C 0 P-图，其中U是G的泛点集。设G是一个C_0 P-图，G的顶点的标号使得M_n（G）的每一列中的0设C1是0在主对角线下方的列的集合 集合C1，C2和C3划分V（G），C3对应于G的泛顶点集合U，并且G[C1]和G[C2]是G中的团（如果顶点vi∈C1不与顶点vj相邻，则第j列和第i行中的对应0必须在对角线上方，因为第i列为0，第j行在下面）。我们用（C1，C2，U）表示这个划分，或者当U = 0时简单地用（C1，C2）表示，然后|C1| ≥ 2且|C2| ≥ 2。同样为了简单起见，我们表示G1：=G[C1]和G2：=G[C2]。由此可知，G是C ~ 0 P-图，（C1，C2， U）（或（C1，C2），当U=0时）是V（G）的上述划分很容易证明下面关于C 0 P-图的最小k元组控制集406M.P. Dobson等人/理论计算机科学电子笔记346（2019）401引理3.3设G是一个C ~ 0 P-图，k是一个正整数。如果|C i|对于i = 1，2，≥ k，则γ×k（G）≤2k.证据设D i∈C i，|D i|= k，对于i = 1，2，并考虑集合D1<$D2。设v∈V（G）.如果v∈C i，则D i<$N G [v]，因此|N G [v]（D1D2）| ≥ |D i|= k，其中i = 1，2.如果v ∈ U，显然D1<$D2<$N G [v]= V（G），因此|N G [v]（D1D2）|为|=2 k ≥ k。|= 2 k ≥ k.则D1<$D2是G的一个k元控制集，上界如下.Q命题2.4允许我们将我们对C_0 P-图的研究限制在具有划分（C_1，C_2）且C_1和C_2是非空集的图上。在这些假设和引理2.1和3.3下，对任意的C_0 P-图G，我们有k+1≤γ×k（G）≤2k。根据[14]中的符号，让我们表示V（G）={v1，v2，···，vn}，C1={v1，v2，···，vr}和C2={vr+1，vr+2，···，vn}. 设M∈（G）的子矩阵由y C i和y C j分别表示为y M C iiC j和yC j. 注意，MC1C1和MC2C2都不等于适当大小的矩阵J。C1C2C1C2图三. C_0 P-图G的M_n（G）的 一 个 概 型 .3.1辅助区间图H_i设G是C_0 P-图，（C1，C2）是V（G）的上述划分我们构造两个区间图H1和H2如下：• 对于每个顶点v i∈C1，从[r + 1，n] N定义一个区间I i，使得如果列v i的连续0对应于顶点vp，...，vp + s其中p ≥ r +1且p + s ≤ n，则I i=[p，p + s] N;• 对于每个顶点v i∈C2，从[1，r] N定义一个区间I i，使得如果列v i的连续0对应于顶点vp，...，v p+ s，其中p≥ 1， p+s≤r，则Ii= [p，p+s]N.我们将考虑v i表示区间I i，对于每个i = 1，.，n.如上构造的两个区间图H1和H2具有区间模型I1={I1，I2，...， I r}和I2={I r+1，I r+2，.， I n}，分别。上述结构的一个例子如图所示四：JMC1 2M*C2C1JM.P. Dobson等人/理论计算机科学电子笔记346（2019）401407v3v4v5v2v1v6图四、 图H1和H2与图1的图G相关。注3.4F或C_0 P-图G具有划分（C_1，C_2， U）且U_1=H，图H_1和H2是由G的子图G−U定义的。很清楚，给定H1的两个相交区间Ii和Ij，其中1 ≤ i/= j ≤ r，存在q，其中r+1≤q≤n满足m<$qi=m<$qj=0。 这意味着vqvi∈/E（G）和dvqvj∈/E（G）. 在其他情况下，giventwonon-intersectingintervalsH1的Ii和Ij，对于1≤ij≤r，对于所有q，我们都有mqi= 1或mqj= 1，r+1≤q≤n。因此在MC<$2C1的每一个chrw中，顶点vi或vj对应的列中至少存在一个1，则对任意q，v q v i∈E（G）或vq vj∈E（G），其中r+1≤q≤n.以类似的方式，上述论点显然对区间图H2成立。3.2H_i的稳定集与G我们用αi表示在前一小节中构造的区间图Hi的独立数，其中i∈ {1， 2}。让我们注意到，区间图的独立数可以在线性时间内找到[6]。我们首先有：引理3.5设G是一个具有划分（C1，C2）的C_0 P-图，S∈C_j，t是一个正整数，使得S_t-支配G_i，其中i = j.然后|S| ≥t +1。是的。 由于U=n，很明显，对于eachvertexv∈Ci，存在一个非邻接顶点w ∈ Cj，其中i i = j且i ∈ {1，2}. 不平等很容易发生。Q因此，很简单，任何子集S∈C i|S|- 优于G i，对于每个1、2、3、4、5、6、7、10、11、12、13、14、15、16、17、18、19、|S|-1）-支配整个图G。当考虑Hi的稳定集时，以下有趣的事实将是下一节结果的关键：命题3.6设G是一个具有划分（C1，C2）的C ~ 0 P-图，且S∈Ci，其中i∈{1，2}.如果是，则S是H的稳定集，当且仅当S（|S| − 1）-优于G j，对于i/=j。证据 S是（|S| G j的-1）-元组控制集当且仅当对每个顶点 v∈C j，|N G [v] S| ≥|S|-1。因此，S是（|S|-1）-元组控制集如果和o-如果对于MCjCi的每一个chr ow，在S中对应于顶点的列中至多存在一个零。这等价于说区间集{I t}t：vt∈S是两两不相邻的，即S是H i的稳定集。Q408M.P. Dobson等人/理论计算机科学电子笔记346（2019）4014C_0 P-图的k在前一节中给出的给定C 0 P-图的元组控制集与由其定义的辅助区间图H1和H2的稳定集之间的关系允许我们陈述C 0 P-图上的k元组控制的以下一般结果定理4.1设G是一个划分为（C1，C2）的C 0 P -图，区间图H i的定义同上，α i是Hi的独立数，对任意i∈ {1，2}. 然后(i) 若α i= 1，D是G 的k-元组控制集，则|D C j|≥ k，1≤i/ =j≤ 2;(ii) 若α1+α2= 2，则γ×k（G）=2k;(iii) 若α1+α2>k，则γ×k（G）=k+1;(iv) 如果α1 + α2 = k，|C i| ≥α i+1，i∈ {1，2}，则γ×k（G）= k +2.证据(i) W.l.o.g.，假设i=1。则α1=1意味着H1中的顶点是两两相邻的。因此，对应的间隔是成对重叠的。众所周知，区间图的区间模型满足Helly性质（关于该性质的定义，例如参见[7]）。因此，存在作为每一个变量的一部分的点因此，在MC<$2C1中有一个rowj只包含0，因此顶点v j ∈ C 2与C 1中的 这意味着|D组C组2| ≥ k.(ii) 若α1=α2= 1，则前一项暗示G的任意k元组控制集至少有2k个顶点.则γ×k（G）≥2k. 等式由引理3.3推导。(iii) 设S1和S2分别是H1和H2的稳定集，|S1和S2|= k +1。从提案3.6 S i|S I|--|S I|− 1）-支配G j，对于每个i，j ∈ {1，2}且i/= j。若S1<$S2是G的一个k元控制集，则γ×k（G）≤k+ 1.由于引理2.1中的γ×k（G）> k，我们得到γ×k（G）=k+1.(iv) 设S1和S2分别是H1和H2显然，S1<$S2是G的一个（α1+α2−1）-控制集，即G的一个（k−1）-控制集，G. 取两个顶点w1∈C1−S1和w2∈C2−S2。集合S1<$S2<${w1，w2}是G的一个k-元组控制集，基数为k+2，意味着γ×k（G）≤k+2.但由于γ×k（G）≥k+1（U=0），所以足以证明γ×k（G）/=k+1. 设D是G的最小k-元组控制集，|D|= k +1，并表示D1 = D<$C1，D2 = D<$C2，d1 = |D1|D 2 =|D2|. W.l.o.g.我们假设α1

下载后可阅读完整内容，剩余1页未读，立即下载