最小偏心等距循环问题的理论研究及NP-Hard性质证明

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）159-169www.elsevier.com/locate/entcs关于最小偏心率等距环问题E'tienneBirmel'e1、FabiendeMontgol fier2和L'eoPlanche3LaboratoireMAP5，Universit'eParisDescartesandCNRS，Sor bonneParisCit'e，Paris，法国1，3IRIF，Universit'eParisDiderot-Paris72，3摘要本文研究了最小偏心等距循环（MEIC）问题。给定一个图，这个问题在于找到一个具有最小可能偏心率k的 等 距 环 。 我 们 证 明 了 这 个 问 题 是 NP-Hard 的 ， 我 们 提 出 了 一 个 3- 近 似 算 法 ， 运 行 时 间 为 O （ n（m+kn））关键词：等距圈;偏心率;k-控制;k-覆盖1介绍对于图分类的目的和应用，将图概括为更简单的对象（如树或路径）或这篇文章的情况下，一个循环。不同的结构和度量，一个特征，例如树分解和树宽度[8]。另一种方法，我们在这篇文章中集中，是研究问题的支配。在路径的情况下，问题在于找到一条路径，使得图中的每个顶点都属于该路径或在该路径中有邻居。 几类图是以主导路径来定义的。[5]中研究了含有控制对的图，即顶点使得连接它们的每条路都是控制的。文[1]中刻画了所有导出子图都存在短控制路的图。寻找支配路径或支配顶点对的线性时间算法也被开发用于无AT图[3，4]。1电子邮件：etienne. parisdescartes.fr2电子邮件：fm@irif.fr3电子邮件：leoplanche@gmail.comhttps://doi.org/10.1016/j.entcs.2019.08.0151571-0661/© 2019由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。160- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）然而，支配路径并不存在于每个图中。支配概念的一个自然扩展是k-覆盖（也称为k-支配）概念对于给定的整数k，如果每个顶点与路径的距离至多为k，则路径k-覆盖图。使得路径k-覆盖图的最小k是所需的度量。这个度量的另一个公式是偏心率的概念。给定一个图G，x∈V（G），S∈V（G），记d（x，S）= mins∈SdG（x，s）. S的偏心率，记为ecc（S），是最小的k，使得对任意x∈V（G），dG（x，S）≤k。最小偏心率最短路径（MESP）问题是由Dragan和Leitert[6]提出的。这个名字是透明的，因为它包含在寻找最短的路径与最小的偏心率。这个问题的研究最初是出于它的链接到嵌入低失真的图形到线。Dragan和Leitert证明了该问题是NP完全的，并设计了一些近似算法，建立了它与线嵌入问题的关系[6]。MESP问题也与生物数据集产生的图形问题有关[2]。与MESP问题相关的一个问题是找到具有最小偏心率的等距循环，如[2]中所定义。一个循环是等距的，如果它保持距离：定义1.1【等距圈】设G是一个图，C是G的圈。dG表示G中的距离，dC表示G[C]中的距离。C是等距圈当且仅当对于C的每两个顶点u，v有：dG（u，v）=dC（u，v）。换句话说，在循环中连接u和v的两条路径之一是图中的最短路径。注意，等长循环必然是诱导循环。我们感兴趣的问题是找到一个具有最小偏心率的等距循环。定义1.2[最小偏心等距圈问题（MEIC）]给定一个图G，找到一个等距圈C，使得对于每个等距圈U，ecc（C）≤ecc（U）。时间复杂度为O（n）。752log（n））时间[7]，这给出了MEIC问题的多项式时间3-近似[2]。还证明了一个允许有低偏心率的等距圈的图允许有低畸变的圈嵌入[2]。在本文中，我们首先证明了MEIC问题是NP-完全的。为此，我们建议将MESP减少为MEIC。然后我们提出了一个O（n（m+kn））时间的3-近似算法。这比O（n）快。752log（n））时间算法，但附加了一个约束条件，即最小偏心率的等距环的大小必须至少是其偏心率的32倍（见定理4.6）。请注意，找到最小偏心率等距循环仅在“甜甜圈形”图中有用- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）161定义和符号通过本文，我们考虑有限连通无向图。 对于图G =（V，E），我们使用n = |V|和m = |E|表示G的点集和边集的基数。两个顶点u和v之间的最短路径是一条路径，在所有u，v-路中，长度最小。它的长度（计算边缘）是距离d（u，v）。当需要精度时，我们用dG（u，v）表示图G中两个顶点u和v之间的距离。根据上下文，我们将路径视为一个序列或一组顶点。顶点v与集合S之间的距离d（v，S）是v与S的顶点之间的最小距离。集合S的偏心率ecc（S）是S到G的任一顶点的最大距离。 球以v为中心，r为半径，记为B（v，r），是距离不超过r的顶点的集合从v。给定两个顶点集A和B，我们记A\B为A的顶点集而不是B。2np完全我们提出了一个多项式减少MESP MEIC。设f是与顶点为V（G）={v1，... v n}是图族f（G）={H（i，j）∈{1. n}2}使得对于每个（i，j）∈ {1. n}2，H（i，j）是在v i和v j之间添加了一条长度为2 n的路Pi，j的图G.引理2.1给定图G，G的最小偏心率最短路的偏心率为k当且仅当f（G）的任一图的最小偏心率等距圈的偏心率至少为 k。证据 证明了对f（G）中的任意图Hi，j，G中的任意最小偏心率等距圈都包含Pi，j和Vi与vj之间的G中最小偏心率最短路.权利要求1：任何在H i，j中具有最小偏心率的等距环都包含Pi，j。考虑G的任意圈C。它不包含Pi，j中除vi以外的任何顶点和VJ。路径Pi，j的长度为2n，循环C在Hi，j中的偏心率为尺寸至少为n。现在考虑Hi，j中包含Pi，j和vi与vj之间的最短路径的任何圈。这个循环是等距的，偏心率最多为n−2。权利要求2：任何在Hi，j中具有最小偏心率的等距环都包含Pi，j，并且G中vi和vj之间的最小偏心率的最短路径。我们已经建立了这样一个循环C包含Pi，j和一条路径Q，在vi和vj之间。此外，Q或Pi，j必须是最短路径，因为C是等距的。距离dG（vi，vj）至多为n−1，Pi，j的大小为2n，Q因此是连接vi和vj的最短路径。此外，由于任何路径之间的最短路径Pi，j的顶点和G的任一顶点都含有vi或vj，ecc（C）=eccG（Q），其中eccG表示图G的偏心率.C是等距圈间的最小偏心率，Q是vi和vj之间的最短路间的最小偏心率。Q引理2.1意味着G中的MESP的解可以通过求解162- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）--MEIC在f（G）中，并且变换f显然是多项式的。MESP是一个NP完全问题[6]，因此：定理2.2 MEIC问题是NP-完全的。3初步结果我们为每个循环C定义一个任意的循环方向，对于循环的每个u，v顶点，我们注意到Cuv和Cvu是C中连接u和v的两条路径。为了使证明更清楚，我们定义算子定义3.1设G是一个图，其等距圈Ck-控制G。对于G中的每个顶点x，XJ表示C中距离x至多为k的顶点，如果有几个选择，则下面的引理是一个重要的初步结果，它将允许我们以后建立3个k-控制圈，如果图包含一个等距圈k-控制它。引理3.2设G是一个具有等距圈Ck-控制的图，u和v是G中的任意两个顶点。 u和v2之间的每条路k-支配Cu′，v′或Cv′，u′.证据证明中使用的符号如图1所示。设P是u和v之间的路径。设P不2 k-支配路径Cn′ ，v′上的某个顶点xb，并考虑在Cn ′，v′中有一个任意顶点a. 我们有一个VEUJ（resp. vJ）在路径Ca，b（resp. Cb，a）.则u在距离Ca，b最多k处，v在距离Cb，a最多k处。此外，由于G的每个顶点与这两条路中的一条路的距离至多为k，所以存在P中的相邻顶点c和d，使得CJ在Cb，a中，DJ在Cb，a中.当d（CJ，DJ）≤d（CJ，c）+d（c，d）+d（d，DJ）≤2k+1且C是等距圈时，C c′，d′或C d′，c′的长度至多为2k+1，且d是y c，d的2k-支配的. 此外，b和a不在cJ和dJ之间的C的相同子路径中，因此a或b都是2k-被{c，d}支配的。由于b不能被P 2k-支配，因此a被{c，d}2k-支配，因此被P支配。前面的断言对Cv′，u′中的每个a都成立，下面的引理。Q4时间复杂度为O（n（m+kn））在这一节中，我们开发了一个新的近似算法的MEIC问题，具有更好的复杂性相比，[2]（定理4），但需要一个图具有更长的等距循环。考虑一个图，其等距圈的偏心率为k。算法1（FirstCycle）首先计算偏心率最大为3k但不为nec的周期U0- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）1631个第一周期输入：图G输出：A周期U02 设a是G3计算b，a是距离a4 计算P从a到b5设m是P中的顶点6如果a和b在G=G\B（m，[m]）中一致，则J|P|7设PJ是GJ中a和b之间的最短路48设c是Pa的顶点，m<$PJ离a最远10返回Pc，d返回PcJ，d9设d是Pm的顶点，b<$PJ离b返回错误“MEIC too shortrelativeCPD一个dJP′CJVJ的v一个uuJ|P|BJBP4CC≤k≤kBMMJ图1.一、 引理3.2（左）和引理4.1（右）中使用的符号基本上是等距的。它的大小，然后迭代减少，同时保持最多3k的偏心率。当最后计算的循环是等距的时，算法结束算法1：算法FirstCycle引理4.1设G是具有k-控制等距圈C的图。如果C的大小至少为26 k + 6，则FirstCycle（G）返回循环U02 k-支配C。此外，U 0的大小至多为|C|+4K，至少|C|-2k-2证据证明中使用的符号如图1所示。如果FirstCycle（G）返回一个循环U0，则它是两条路径P和PJ的并集。让164- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）4| || || || |4444| |m是P的中间的顶点（在两个可能的顶点中随机选择，如果-P-是奇数），并假设w.l.o.g. mJ在C a′b′中。1. P的长度至少为12 k。设aJ是C中离a j最远的一个顶点。ecc（a）≥d（a，aJ）≥d（aJ，aJ）−kC≥[2] − k≥12k +3由于b是G中离a最远的一个顶点，所以我们有这个结果。权利要求2：B（m，[|P|D）D OESNOTDis conn ectafromb.考虑在Cb′a′中的一个y顶点y，在Ca′b′中的一个smJ，d（m，y）≥d（mJ，y）−d（m，mJ）≥min（d（mJ，aJ），d（mJ，bJ））−k但d（mJ，aJ）≥d（a，m）−d（a，aJ）−d（m，mJ）P≥[2<$−2k使得d（mJ，bJ）≥d（b，m）−d（b，bJ）−d（m，mJ）P≥[2<$−2kd（m，y）P≥[2<$−3kP≥[4]+[|P|♩− 3k >[ |P|4因此，C b′a′是t距离at最小[|P|M. 为了更好的生活，d（a，m）= |P||P|+ 3k[二 ≥[ 4♩d（b，m）= |P||P|+ 3k[二 ≥[4♩因此，从a到aJ和b到bJ的长度为k的路径的距离大于[|P|m + 2 k。因此，顶点a和b在GJ中连通。这个声明意味着FirstCycle（G）返回一个循环。结论3：U 02 k-优于C.在不损失一般性y的情况下，假设mJ在C c′d′中。 首先证明Pcm2k-优于Cc′m′. 要做到这一点，假设情况并非如此。 则由引理3.2，Pcm2k-支配Cm′c′. xmJ存在于Cc′d′中，则dJ在Cm′c′中，且在Pcm中存在一个顶点x，该顶点x与dJ的距离不超过2k.因此，|= d（c，x）+ d（x，m）|= d (c, x)+ d (x, m)|≥ d（c，d）− 3 k + d（d，m）− 3k d（c，m）≥ d（c，m）+ d（m，d）+d（d，m）− 6 k| ≥ d (c, d) − 3 k + d (d,m) − 3 k d (c, m) ≥ d (c, m)+ d (m, d)+d (d, m) − 6 k6k≥ 2d（d，m）因为d是P j的顶点，所以它的距离大于[|P|从m开始，它遵循，P6k≥[2]♩- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）165这与P的尺寸大于12 k的事实相矛盾，因此Pcm2 k-优于Cc′m′。 同样地，我们证明Pmd2k-支配Cm ′d′，从而得出P2k-支配Cc′d′.166- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）42引理3.2更进一步暗示PJ2k-支配Cc′d′或Cd′c′. But，as[|P|如果G j大于3 k，则mJ不能被G j中的一个顶点2k-支配. 当MJ在Cc′d′上时，PJ2k-支配Cd′c′. 由此得出U02k-优于C.权利要求4：|C| − 6 k − 2 ≤ |U 0| ≤ |C|+4 k|≤|C a ′ b′|P 是 a 和 b 之 间 的 最 短 路 径 。 |+2kasPisa shortestpath betweenaandb. 类似地，由于PJ是Gj中的最短路径，|PJ| ≤|C b′a′|+2k。 结果呢，|P|+的|PJ| ≤|C|+4k。另一个不等式是引理4.2的直接结果。结论5：U0不包含两次相同的顶点假设顶点x在U0中出现不止一次。因为P和PJ都是最短路径，所以它们每个都最多（并且恰好）包含一次x。 如果x在Pc，m中，那么它离a比离c远，它应该在第8行被选择而不是c。这就产生了矛盾。如果我们假定x在Pm，d中，也会出现同样的矛盾.Q引理4.2设G是一个图，其等距圈Ck-控制G. 让一个b是两个顶点，可能a= b，linkedbyapathP2k-控制Ca′，b′。你好，|≥| C a ′ b′|-6k-2| −6 k−2.特别地，如果U是圈2k-控制C，则U的大小至少为|C|-6k-2证据考虑任意两个顶点a和b以及连接它们的路P和2k-控制的C a′，b′。设m是2k-控制m的P的C a′，b′和z的中间点. Ca′，m最长的长度|C||、|C a′，m| ≤d（AJ，m）+1。 同样，|C m，b′| ≤d（m，b，J）+1。它遵循|≤ d（a j，m）+ d（m，b j）+ 2 ≤（k+| Pa，z|+2 k）+（k +|Pz，b|+2 k）+2|+2k) + 2≤|P a，b|+6 k +2关于循环的a的重新定义如下：选择a=b。Q函数FirstCycle创建了一个圈U0，不一定是等距的，3k-支配图。从U0开始，循环的大小通过算法2描述的NextCycle过程迭代地减小，同时保持3k-支配性质。引理4.3设G是一个含有等距圈C的图，G是k-控制图。对于每个路径P，存在C的子路径I（P），使得：• 在P的距离不超过k处的C的每个顶点都在I（P）中，并且I（P）是这样的顶点;• P ~2k-支配I（P）证据证明中使用的符号如图2所示。设UJ和VJ是C的两个顶点，使得u和v都属于P，并证明P2k-支配Cu′v′（证明存在一对顶点对，因为我们通常都是pickuj=VJ）.- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）167PI（P）KKC1次下一循环输入：一个图G和一个圈Ui输出：A周期Ui+12fora∈Uido3如果45S={b |dU i（a，b）=[2π和d G（a，b）4k则意味着YJ不在Ca′，w′中。我们现在要研究三种不同的子情形，分别对应于y∈Ua，w，y∈Uw，b和y∈Ub，a，但它们的论证是非常相似的.设y∈U a，w，如图3右边所示。 让我们把U分解为U=Uy，w<$（Uw，b<$Ub，y）. 通过定义wJ，I（Uy，w）包含C y′w′。因此|≥| C y ′，w′|− 6 k − 2≥| C|− d（y j，z）− d（z，w j）− 6 k − 2 ≥| C|-14k-3| −14k−3.I（Uw，b）包含Cb′，w′b，y定义WJ，I（Ub，y）包含Cy′，b′by定义w1J。 因此，I（Uw，b<$Ub，y）包含C y′，w′，|Uw，bUb，y| ≥|-14 k-3| − 14 k − 3.最后，2（|C| − 14 k− 3）≤|C|+4k，即|C| ≤ 32 k + 6，这是一个矛盾。设y∈Uw，b.让我们将U分解为U=Uw，y<$（Uy，b<$Ub，a<$Ua，w）。通过定义wJ，I（Uw，y）包含C y′w′，因此|Uw，y| ≥|C y′，w′| −6k−2≥|− d（y j，z）− d（z，w j）− 6 k − 2 ≥| C|-14 k-3| − 14 k − 3.因此，I（Uy，b）包含Cy′，b ′b，b ′b，w定义w2J，I（Ub，a）包含Cb ′，a′，I（Ua，w）包含Ca′，w′b，w定义WJ，因此I（Uy，b<$Ub，a<$Ua，w）包含Cy′，w′. 因此，它的长度也更大，|C| -14k-2这再次暗示，|C| ≤ 32 k + 6，这是一个矛盾。最后，假设y∈Ub，a。让我们将U分解为U=（Uw，b<$Ub，y）<$（Uy，aUa，w）.I（Uw，b）包含Cb′，w′b定义为wJ，I（Ub，y）包含Cy′，b′b定义为w1J。 因此，I（Uw，b<$Ub，y）包含C y′，w′，|Uw，bUb，y| ≥|C| -14k-3 因此，I（Uy，a）包含Cy′，a′，因为它不包含Ca′，y ′ b，y ′b，h′s，且I（Ua，w）包含Ca′，w ′ b，y ′b，w ′b，J的定义. 因此，我（Uy，aUa，w）C y′，w′和|Uy，aUa，w| ≥|C| -14k-3这再次暗示，|C| ≤ 32 k +6，导致矛盾。Q引理4.5设G是一个图，其等距圈C是k-控制的，且G的大小至少为32 k +7。- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）169甲乙丙甲乙丙甲乙丙细介绍细介绍我I（ Ua，b）U一个一ww2JWJCBJBI（ Ua，b）U一个J一yw2JbJbWJyJzC图三. 引理4.4的证明中使用的符号，在左边的情况1和右边的情况2中设Ui是一个循环，使得：•Ui2k-优于C.• |C| −6k−2≤|U i| ≤|C|+4k则U i+1=NextCycle（U i）具有相同的性质，|U i+1|<|Ui|.证据在引理4.2中，关于长度的不等式是直接的，并且U i+1是通过将U i的弧替换为更小长度的路径而获得的。为了证明2k-支配，考虑由算法选择的连接Ui的顶点a和b的路径Q根据引理3.2，可以假设w.l.o.g. I（Q）包含C a′，b′，因此2k-支配它. 因此，Lemma4.4意味着，我我Cb′，a′包含在I（Ua，b）或I（Ub，a）中. 通过对称性，假设它包含在a、b）。那么，I（Q<$Ui）=C，并且由此得出Q<$Ui2k-支配C并且是偏心率最大为3K。如果U i+1= Q<$U i，则该性质成立。如果Ui+1=Q<$Ui，QUi也是3k-支配G，因为它具有较低的偏心率。我引理4.4则意味着Ub，a或Q2k-支配Cb′a′，因此ib，a 2k-优于C.Q算法FirstCycle需要计算3棵BFS树，其复杂度为O（m）。复杂性瓶颈是在NextCycle的第3行中测试n2个顶点对上的If条件。G内部的距离dG可以在O（nm）内预先计算。时间使用nBFS，而如果顶点被编号，则评估循环内的距离dUi因此，时间复杂度为O（n）。当找到一对（a，b）时，直到第6行的块花费O（m）时间，再次使用三个BFS，并且只完成一次。因此算法6（NextCycle）需要O（n2）时间。由引理4.5可知，序列U i的圈的长度严格递减，并且至少为|C|-6k-2 作为|U 0|≤ |C| +4 k，则序列在至多一次FirstCycle执行和至多10 k +2次执行之后收敛关于NextCycle不忘记O（nm）时间距离预计算，我们有：I（U）QU170- 是的Birmelé et al. /Electronic Notes in Theoretical Computer Science 346（2019）1次近似循环输入：图G输出：一个周期2 U=第一次循环（G）3 V=NextCycle（G，4当V/=U时5U=V6V=NextCycle（G，V）7 返回V算法3：ApproximationCycle算法的伪代码定理4.6设一个图的等距圈的偏心率为k，且长度l≥32k + 7，则一个图的等距圈的偏心率至多为3k，其计算时间为O（n（m + kn））.引用[1] 巴奇奥，G.，Z. Tuza和M. Voigt，由inducedpaths支配的graphs的特征化，离散数学307（2007），pp.822-826[2] Birme l'e ， E'. ， F.deMo ntgol fier ， L.计 划 C 他 和 L 。 Viennot ， D ecom posingagraphintoshortestpathswith bounded eccentricity，in：28th International Symposium on Algorithms andComputation（ISAAC），2017，pp. 15：1-15：13。[3] Corneil，D. G.，S. Olariu和L. Stewart，A linear time algorithm to calculate a dominant path in an AT-free graph，Inf.过程Lett. 54（1995），pp.253-257[4] Corneil，D. G.，S. Olariu和L.刘晓波，无三圈星形图，北京大学出版社，2001。Comput. 28（1999），pp.公元1284-1297年。[5] 德奥贡，J.S. 和D. 张文，等，离散数学，2001（2002），pp. 353-366.[6] Dragan，F.F. 和A.Leitert，关于最小偏心率最短路径问题，理论计算机科学694（2017），pp.66比78[7] Lokshtanov，D.， 求图中的最长等距环，离散应用数学157（2009），pp. 2670-2674。[8] Robertson，N.和p.D. 西摩，小图。I. 不包括森林，组合理论杂志，系列B 35（1983年），页。39比61