没有合适的资源?快使用搜索试试~ 我知道了~
二次时间可解问题的复杂性及其与强指数时间假设的关系
O可在www.sciencedirect.com在线获取理论计算机科学电子笔记322(2016)51-67www.elsevier.com/locate/entcs进入广场一类二次可解问题的复杂性Michele Borassi1IMT Institute for Advanced StudiesLucca,意大利Pierluigi Crescenzi2佛罗伦萨大学信息工程学院意大利佛罗伦萨Michel Habib3LIAFA巴黎狄德罗大学法国巴黎摘要我们分析了几个二次时间可解的问题,我们证明了这些问题在真正的次二次时间(即,在时间(n2−c)中,对于某些n> 0)是不可解的,除非著名的强指数时间假设(简称SETH)是假的。特别地,我们从一个人工二次时间可解的问题的k-S卡普约简,证明了一个真正的次二次时间算法在网络中的任何问题伪造SETH。其中一些结果是已知的,而另一些据我们所知是新的。 的 考虑的新问题是:计算顶点的介数中心性(证明了相同的结果Abboud等人独立地提出),计算图中的最小接近中心性,计算图的双曲性,以及计算集合的子集图。 另一方面我们我将证明测试一个有向图是否是传递的和测试一个图是否是可比较图是次二次时间可解的(我们的算法是实用的,因为它不是基于复杂的矩阵乘法算法)。关键词:二次算法,约简,强指数时间假设,传递闭包1电子邮件:michele. imtlucca.it2电子邮件:pierluigi. unifi.it3电子邮件:habib@liafa.univ-paris-diderot.frhttp://dx.doi.org/10.1016/j.entcs.2016.03.0051571-0661/© 2016作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。52M. Borassi等人/理论计算机科学电子笔记322(2016)511介绍从理论计算机科学的一开始,直到最近几年,NP难问题和多项式时间可解问题之间的对偶性一直被认为是区分“容易”和“困难”问题的阈值。然而,多项式时间算法可能并不像人们期望的那样有效:例如,在具有数百万或数十亿节点的真实世界网络中,二次时间算法在实践中也可能太慢,而真正的次二次算法将是一个显著的改进,如果一个算法的时间复杂度为O(n2−n),其中n是输入大小,则该算法被称为真正的次二次算法。遵循NP完全性理论背后的主要思想,并且无法证明一个特定的多项式时间可解问题可能会或可能不会接受更快的算法,研究人员最近开始证明这样一个算法的存在将意味着其他众所周知和广泛研究的问题的更快解决方案。作为一个例子,大量的工作开始于对3SUM问题的分析,该问题包括,给定三个整数集合A,B和C,确定是否存在a∈A,b∈B和c∈C,使得a+b+c= 0。这个问题已经得到了广泛的研究,据我们所知,最著名的算法是次二次的[6](也就是说,它们的时间复杂度是O(n2)),但不是真正的次二次的(也就是说,它们的时间复杂度不是O(n2−n)),对于任何0)。最近,在[25]中,也证明了3SUM问题的决策树复杂性是真正的次二次的,但是这个结果不足以提供真正的次二次算法。因此,3SUM问题已经成为证明许多其他问题的“硬度”的起点 注意,所有这些结果都不处理完备性的概念,但他们只是证明“一个问题比另一个问题更难”,使用问题之间的一种归约,依赖于最简单的问题已经研究了多年,没有找到有效的算法。沿着这个研究方向的一个最近的发展是基于强指数时间假设(SETH),用作证明多项式时间可解问题的难度的工具。 这个假设说,没有算法可以在O((2−n)n)时间内解决k-SAT问题,其中n>0不依赖于k[27]。研究人员已经使用这个假设来证明硬度结果,从[38]开始,其中,在许多其他结果中,证明了TWO DISJOINTSETS问题在真正的次二次时间内不可解,除非SETH是假的(在[38]中,TWO DISJOINTSETS问题被命名为Cooper-ti-VE S ubSETQUER y)。相反,在[40]中,对于几个问题,证明了它们要么都有真正的次立方算法,要么都没有。 SETH也在[35]中使用,其中证明了该假设被某些具有特定多项式时间复杂度的问题的算法的存在所证伪在[1]中发表了更一般的结果,其中考虑了介数中心性,到达中心性,半径,中位数和直径,并且其中考虑的参数是节点数而不是输入大小(例如,负三角形问题,3时间复杂度为O(m2),也就是说,时间复杂度为O(m 2)。真正的次二次时间)。在这个领域的其他结果中,我们发现[36,37,2,10]。M. Borassi等人/理论计算机科学电子笔记322(2016)5153二部图的支配顶点图支配顶点Sperner家族最大简单集族子集图k-Sperner家族两个不相交集二元向量的可积性v的介数中介中心性k-两个不相交集最 小 接 近中心性双曲性分割图k-Sat*直径2或3图形直径2或3双曲性固定顶点k-2覆盖矩阵乘法二分子集2-控制集双固定点双曲性两个覆盖本地字符串对齐二部3-控制集3-控制集1.1我们的贡献虽然许多硬度的结果已经公布,到目前为止,有没有调查包含他们所有(现有的文件开始从k-S问题,而不是通过更简单的问题,如两个DISJOINT集问题)。如图1所示,在本文中,我们收集了迄今为止已证明的许多约简,我们将它们放在一个统一的框架中,最重要的是,我们使用这种分析来证明新的约简。请注意,与其他作品不同[40,1],我们考虑的参数是输入大小而不是节点数量:如果考虑稀疏图(例如,大多数现实世界的复杂网络),这种分析更适合。更具体地说,新的约简处理以下问题。Fig. 1.本文提供的减少网络。 灰色的问题表示原始结果,白色的问题表示已知的结果,浅灰色的问题表示中间步骤,尽管如此,这些步骤本身也可能是有趣的,比如SSPLIT G D i2OR 3问题。介数中心性(BETWEENNESSCENTRALITY)是一个广泛使用的与社区结构相关的图参数。特别地,顶点v的介数中心度被定义为在所有与v不同的节点s和t对上,从s到t通过v的最短路径的数量与从s到t的最短路径的数量之间的比率的总和(更多信息,参见[22,33]及其参考文献)。尽管有许多作品,如[9,4,17],没有真正的次二次算法计算介数中心是已知的,即使是一个单一的顶点(B介数 CENTRALIT yV)。在[4]中,54M. Borassi等人/理论计算机科学电子笔记322(2016)512他说,找到更好的结果来近似所有顶点的介数中心是一个“具有挑战性的开放问题”。我们的分析不仅证明了在次二次时间内计算所有顶点的介数中心性是违反SETH的,而且还给出了计算单个顶点的介数在[1]中,通过从直径计算问题的简化独立地证明了相同的结果图分析中的另一个基本参数是接近中心性,1950年首次定义[7],最近在分析现实世界的网络时重新考虑(对于感兴趣的读者,我们参考[31]及其参考文献)。顶点v的接近中心度定义为从v到任何其他顶点w的所有距离d(v,w)之和的倒数。这个参数也引起了算法的兴趣,最近的结果是一个非常快速的算法来近似所有顶点的接近中心[13]。本文将证明关于此测度寻找“最小中心”顶点的困难性。这个结果的简单后果是,在真正的次二次时间内计算所有顶点的接近中心性,或提取一个“足够小”的集合包含所有外围顶点的难度图的Gromov双曲性[24](也称为δ-双曲性[12])最近引起了网络分析领域研究人员的注意[19],并且与图的弦性[41]以及直径和半径计算[12,16]有关 。 顶 点x , y , v , w 的 4 元 组 的双 曲 性 等 于 δ ( x , y , v , w ) =1(S1−S2),其中S1是d(x,y)+d(v,w),d(x,v)+d(y,w),d(x,w)+d(y,v)中的最大和,S2是第二大和。一个图的双曲性是指它在所有4-元组上的最大双曲性。因此,一个简单的算法需要时间O(n4). 在[14]中,提供了一个更好的算法:时间复杂度仍然是O(n4),但它在现实世界的网络中更有效。最后,这个界限在[ 21 ]中得到了改进,其中作者描述了一个时间复杂度为O(n3)的算法。时间复杂度为O(n 2),时间复杂度为O(n2)。69)对于固定顶点v,形式为(v,x1,x2,x3)的4元组的最大双曲性。本文还给出了这一问题的一个困难结果,即一个时间小于O(n2. 05)对于后一个问题将意味着更快的算法(最大,最小)矩阵乘积。在这里,我们将使用另一种方法:我们将证明识别双曲性为1的图在真正的次二次时间内是不可解的,除非SETH是假的。此外,如果我们固定一个顶点v,即使我们固定4元组中的两个顶点v,w,也会有相同的结果(注意,后一个问题是二次时间可解的)。SU bSETG:给定一个基集X的子集的集合C,这个问题要求计算C的子集图。子集图被定义为顶点是C的元素的图,并且它包含边(C,CJ),如果CCJ. 对于这个问题,第一个次二次算法在[42]中提出,在[34,18]中证明了匹配下界。然而,这些下限是基于子集图中的边的数量,这可能是M. Borassi等人/理论计算机科学电子笔记322(2016)5155除了对数因子外,它与输入大小成二次关系。我们的结果表明,计算子集图的复杂性并不因的输出大小,但它是内在的:特别是,我们将证明,即使决定是否子集图没有边是困难的。这排除了真正的次二次算法来检查解决方案是否正确的存在,或者对于输出稀疏的情况,真正的次二次算法的我们将在我们的减少网络中包括几个“中间”问题。其中,我们有一些在图中找到控制集的变化(这是21个Karp的NP完全问题之后一个结果是重要的,因为它意味着很难精确计算包含分裂图的一类图的直径:例如,弦图,其中可以近似直径,加性误差至多为1 [12]。这些结果的硬度证明是已知的,无论是作为“隐藏”的步骤,证明已经出现在文献中,或作为简单的推论以前的工作。然而,我们认为强调这些中间结果是很重要的,因为它们本身可能很有趣,而且它们可能在现有证明的简化和新证明的设计中很有用。在积极的一面,我们证明了两个问题,承认次二次时间al-出租:测试,如果一个图是传递的,测试,如果它是一个可比图。这两个结果将遵循一个新的分析,这将证明一个已知的纯组合算法[23],计算传递闭包有运行时间3时间复杂度为O(m2logn)。使用矩形矩阵乘法可以得到相同的结果阳离子[39],以及一些技巧:然而,我们专注于组合对应物,因为它不包含隐藏在O符号中的大常数,并且它更实用,更容易实现。1.2本文结构在第2节中,我们将定义我们将要分析的一些问题,我们将引入拟线性约化的概念,而在第3节中,我们将证明新的硬度结果(所有其他约化的证明都包含在本文的扩展版本中[8])。第4节给出了传递图和可比图的识别结果。第五节总结全文,并提出一些有待解决的问题。2初步定义和结果我们约简的起点是k -S的一个问题:k-S AT *。输入:两组相同大小的变量X={xi},Y={yj},一组C,56M. Borassi等人/理论计算机科学电子笔记322(2016)512..Σ Σ2O122m2−c子句,使得每个子句最多具有大小k,以及两个幂集P(X),P(Y)(用于改变输入大小)。输出:如果对所有变量的求值满足所有子句,则为True否则就是假的。值得注意的是,该问题与经典问题的区别仅在于输入的大小。这样,存在二次时间算法(尝试所有可能的eval-M评估)。 然而,如果m是变 量 的数量并且n = 2 2, 是输入size,因为X和Y的大小都是m,所以在时间O(n2−n)内运行的算法,其中n不依赖于k,这意味着在时间上求解k-SM(二)(2−n))=O2,其中m是变量的个数。 后一种结果与Seth矛盾。在定义了“开始”问题之后定义2.1从问题P到问题Q的拟线性Karp归约是从P的实例到Q的实例的函数Φ,对于P的每个实例I,满足以下两个性质。• Φ(I)可以在时间O(s(I))中计算,其中s(I)是输入I的大小。4• I和Φ(I)具有相同的输出(如果输出不是布尔值,我们还需要一个线性时间可计算函数,将Φ(I)的输出转换为I的输出)。如果存在从P到Q的拟线性约化,我们将写P ≤qlQ。注2.2若P≤qlQ,且存在一个在时间O<$(n2−<$)内求解Q的算法,则nPc n可在时间O<$(n2− <$)内求解.我们将提供的约简总结在图1中(问题的定义在正文中或附录A中)。前面的注释意味着任何这些问题的O(n2−n)时间算法都将证伪SETH。虽然图中的许多约简是已知的,但有些约简是新的,它们涉及以下在网络分析领域广泛使用的图参数。定义2.3给定一个图G=(V,E),一个顶点V是,s,t∈V,s=/v从s到t通过v的最短路径数 .从s到t的最短路径数不定义2.4给定一个图G =(V,E),顶点v的贴近中心度定义为:v∈Vd(v,w),其中d(v,w)是v和w之间的距离。定义2.5给定一个图G=(V,E),一个4元组顶点的双曲性x,y,v,w是δ(x,y,v,w)=1(S1−S2),其中S1是d(x,y)+4对于某个固定的k,O(f(n))意味着O(f(n)logkn)。M. Borassi等人/理论计算机科学电子笔记322(2016)5157d(v,w),d(x,v)+d(y,w),d(x,w)+d(y,v),S2是第二大和。一个图的双曲性是指它在所有4-元组上的最大双曲性我们将特别考虑以下问题。问题:BETWEENNESS CENTRALIT yV。输入:一个图G=(V,E)和一个顶点v∈V。输出:v的介数中心性。问题:中间性CENTRALIT y。输入:图G=(V,E)。输出:每个顶点v∈V的介数中心性。问题:最小C封闭性 CENTRALIT y。输入:图G=(V,E)和阈值σ。输出:如果存在接近中心度小于σ的顶点,则为真,否则就是假的。问题:HyPERBOLI cIT y。输入:图G=(V,E)。输出:G.问题:HyPER WITH AFIXED VERTEX。输入:一个图G=(V,E)和一个顶点x。输出:δ(x,y,v,w)的每个顶点三元组y,v,w上的最大值问题:HyPER WITH 2FIXEDVERTI cES。输入:图G=(V,E)和两个顶点x,y。输出:δ(x,y,v,w)的每对顶点v,w上的最大值。问题:SU bSET G。输入:集合X和X的子集的集合C。输出:图G=(C,E),其中,对于每个C,CJ∈ C,(C,CJ)∈E当且仅当C<$CJ。3新的硬度结果在本节中,我们证明了图1中包含的新的(即灰色)约简,除了介数中心性之外,介数中心性也在[1]中独立证明。所有其他的证明都可以在本文的扩展版本中找到[8]。所有这些约简都是从k-T两 D不相交集问题出发的.问题:k-T WO D ISJOINTSETS.输入:集合X和X的子集的集合C,使得|X|<0.0000000000000000000000000000000000000000000000000000000000000000058M. Borassi等人/理论计算机科学电子笔记322(2016)51000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |C|).M. Borassi等人/理论计算机科学电子笔记322(2016)5159J第一章|X| −C ′/=C |CJ|=(|C|− 1)|X| −C ′ ∈C|CJ|+的|C|. 那么(x,C)的远度为:输出:如果有两个不相交的集合C,CJ∈ C,则为True,否则为这个问题的困难性由下面的定理证明,其证明也出现在本文的扩展版本[8]中。定理3.1([38])对于每个k,k-S在* ≤qlk-T两个D是相交的集.3.1亲密的硬度定理3.2k-T两个D ISJOINTSETS≤qlM minimumCloseness C entrality.证据我们将尝试最大化距离,而不是最小化接近中心性,这是接近中心性的倒数,即从v到另一个顶点的所有距离之和。我们将构建一个图,其中具有最大远度的顶点对应于C中的集合,并且远度的值不依赖于对应的集合,如果该集合与任何其他集合不相交。如果不满足后一个条件,则顶点的远度更大。特别地,让我们考虑一个例子I=(X,C)ofk-TWODISJOINTSETS,让我们假设X∈/C,让我们用下面的方式构建一个图:• V=V1<$V1J<$V2<$V3,其中V1和V1J是X的两个不相交的副本,V2=C且V3={(x,C)∈X× C:x∈/C};•V1<$V1J是团;• 对x∈V1<$V1J和C∈V2,存在从x到C的边当且仅当x∈C;• 对于每个(x,C)∈V3和CJ∈V2,这些顶点之间存在一条链路当且仅当C =C.断言:最远的顶点在V3中.证据 [权利要求的证明]对于每个顶点v∈V2,考虑顶点w∈V3链接到v. 很明显,从w到任何其他顶点的所有最短路径都必须经过v(这是唯一链接到w的顶点)。这意味着w的距离大于v的距离。对于每个顶点v∈V1<$V1J,我们考虑一个与v相连的顶点w∈V2. 的只有那些比v更靠近w的顶点才是V3中连接到w的顶点,因为w的每个相邻顶点都是v的相邻顶点。这些顶点通过以下方式确定w的距离:|X| − |C|,其中C是对应于w的集合。但2、(|X| − |C|)V1<$V1J中的顶点链接到v而不是w(不在C):这证明了w的距离大于v的距离。Q在这一点上,让我们考虑V3中顶点的远度.特别是,让(x,C)是V3的一个元素,使得C<$CJ对每个CJ都是:可以通过考虑表1中的顶点类来精确计算。在计算f(x,C)的距离之前,我们计算f(x,C),C|X| −|CJ|=(|C|−60M. Borassi等人/理论计算机科学电子笔记322(2016)51. ΣΣΣn∈CJC′C表1从(x,C)到另一个顶点设置顶点种类Number距离(x,C)V1V1′V1V1′V2V2V3V3顶点在C中顶点在C外C′/=C(x′,C)(x′, C′),C′=/C2 |C|二(|X| − |C|)1|C| − 1|X| − |C|C'/=C|X| − |C′|2313244 |C|2016年10月26日,|X| −|C|) + 1 +3(|C|1)+2(|X| −|C|) + 4美元|X| −|CJ|⎞⎠==4个|C|+8 |X| − 8 |C|+1+3 |C|03 - 04 - 0 |C|− 1)|X| − 4|CJ|+4|C|为C′∈C=4个|C||X| − 4|CJ|+3 |C|+4 |X|-2。C′∈C注意这个值并不依赖于所选择的特定(x,C)(这是我们构造的主要目标)。 很明显,如果C<$CJ=<$,则每个顶点(x,C)和(x,C)的 远 度都大于先 前计 算 的值。因此,存在两个不相交集当且仅当在整个图中存在远度大于4的顶点|C||X|04 - 04(C′ |CJ|)+3 |C|+4|X|-2,并且这个值和底层图都 可以在线性时间内计算。Q3.2双曲性的硬度为了证明双曲性问题的困难性,我们将“通过”以下问题,与图的直径(即两个问题:G D i2OR 3。输入:一个图G。输出:如果G的直径为2,则为True,否则为False。定理 3.3 ([36])k-T两个D ISJOINTSETS≤qlG DI ≤ 20 R 3.文[36]中上述定理的证明包含了从k-SAT问题到G DI2 OR 3问题的所有步骤。相反,这些步骤在本文[8]的扩展版本中出现的证明中是分开的,以显示一个有趣的中间问题的难度,即在分裂图的情况下(因此,在弦图的情况下)计算直径。本节的其余部分致力于证明,所有hyper- bolicity问题是困难的比G DI2 OR 3。让我们从陈述两个引理开始。M. Borassi等人/理论计算机科学电子笔记322(2016)5161−22引理3.4([14],引理5)设x,y,v,w是一个4元组,设S1=d(x,y)+d(v,w).则δ(x,y,v,w)≤d(x,y)且δ(x,y,v,w)≤d(v,w)。引理3.5([15],引理3.1)对于每个四元组x,y,v,w,双曲度δ(x,y,v,w)小于或等于四元组中两个顶点之间的最小距离。在证明所有双曲性问题的困难性时所用的构造给定一个输入图G=(V,E),用于G∈ DI ∈ 2OR 3问题,对应的双曲性问题的图是H=(VJ,EJ),被定义为以下几种。集合VJ是{x} <$Vx<$V<$$>{z} <$Vy<${y},其中Vx,V和Vy是V的不相交副本,x,y和z是新顶点。 集合EJ定义为如下所示:• x连接到Vx中的每个顶点,y连接到Vy中的每个顶点,并且z连接到Vx中的每个顶点和Vy中的每个顶点;• Vx和Vx中的相应顶点与Vx和Vy中的相应顶点连通;• 若(v,w)是G的nedG,则V中v和w的拷贝是有联系的通过这种构造,如果x,y是上述顶点,v,w是V中的一对顶点,则2δ(x,y,v,w)=d(x,y)+d(v,w)−max(d(x,v)+d(y,w),d(x,w)+ d(y,w))d(y,v))= 4 + d(v,w)4 = d(v,w),d(x,y)+d(v,w)是最大和。通过构造,V_n中两个顶点之间的最短路保持在V_n中,或者它们的长度至少为4。这意味着maxv,w∈V<$δ(x,y,v,w)=Maxd(v,w)˜至多为1,当且仅当两个之间的最大距离v,w∈V<$2V的顶点数至多为2,当且仅当G的直径至多为2。 为了在此基础上,我们证明了H中的其它4元组具有较小的双曲性,使得H的双曲性正好是G的直径的一半。引理3.6H中的每个4元组的双曲性,其形式不是x,y,v,w,其中v,w∈V最多为1。证据让我们考虑一个双曲性大于1的4元组v,w,vJ,wJ,让我们首先证明x和y属于这个4元组。 这是因为,根据引理3.5,这些顶点中的任何一对之间的距离至少为2,并且2δ(v,w,vJ,wJ)≤S1−4。如果我们想要双曲性大于1,我们需要S1大于6,并且S1中的距离必须至少为4。由于H中唯一的这样的距离是d(x,y),x和y必须在4元组v,w,vJ,wJ中,正如我们想要证明的那样。我们的结论证明表明,双曲性的4元组x,y,v,w,其中v∈/V∈至多为1。如果v=z,这成立,因为d(z,w)≤2每个w,因此根据引理3.4δ(x,y,z,w)≤1。如果v∈Vx(resp.v∈Vy),则δ(x,y,v,w)≤1,因为d(x,v)= 1(分别d(y,v)= 1),我们可以使用引理三点五Q62M. Borassi等人/理论计算机科学电子笔记322(2016)51由于这个引理,我们可以得出我们的约化,因为H的双曲性大于1当且仅当G的直径大于2。既然我们M. Borassi等人/理论计算机科学电子笔记322(2016)5163CC¯¯已知x和y属于具有最大双曲性的4元组,所有双曲性问题的困难性都来自于直径计算的困难性定理3.7G = 20 R3 ≤qlHy,每W为2F混合V。G = 20 R3 ≤qlHy/W × AF ×VERTEX。G = D = 20 R3 ≤qlHy PERBOLIC c IT y.3.3计算子集图的困难性为了证明计算子集图的困难性,我们将证明判断子集图是否为空是困难的。当且仅当给定一个基集X和X的子集的集合C,不存在元素对C,CJ∈ C使得C<$CJ。如果我们把自己限制在X相对于C很小的情况下,我们就把SU b集 GN问题简化为下面的问题。问题:k-S PERNER F AMIL y.输入:集合X和X的子集的集合C, 使得|X|<0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |C|).输出:如果有两个集合C,CJ∈ C使得C<$CJ,则为True,否则为False。我们将通过下面的定理证明这个问题的困难性来结束证明。定理 3.8k-T两个D不相交集≤qlk-S PERNER F AMIL y.证据考虑一个k-T两个D相交集的实例I =(X,C).首先,我们定义ΦJ(I)=(X,CJ),其中CJ=C <$C<$,andndC<$:={X−C:C∈C}(这不是正确的定义,但我们将看到如何修改它)。 如果我们找到两个集合C ∈ C,CJ∈C<$使得C<$CJ,我们知道C和X-CJ不相交且在C中,所以我们找到了一个解。然而,当我们解决k-S PERNER F AMIL y问题时,我们不确定C∈ C和CJ∈C<$:我们将通过稍微修改XJ和C J来解决这个问题。 为了避免存在C,CJ∈ C使得C<$CJ,我们定义 2、[001 - 2010] 001 - 2010)C),我们将两个集合Y ={y1,...,|||y k}和Z={z1,...,z k}到X.然后,我们将Y和Z添加到C的每个集合中,并将一些y i和一些z j添加到每个元素C∈ C,使得C中没有元素可以支配C中的另一个元素(例如,我们可以将每个集合C与具有k的唯一二进制数相关联位,并使用y i作为0和z j作为1对该数字进行编码)。这样,我们就保持了C中的集合和C中的集合之间的支配关系,并且我们也避免了C中的集合支配中的集合。最后,我们需要避免两组 主宰每一个Other:只需要在相同的构造中添加对数大小的新集合YJ和ZJ,并使用它们来唯一地编码C中的任何元素。为了保持C和C¯之间的支配关系,YJ和ZJ中的任何元素都不会添加到C中的子集中。Q64M. Borassi等人/理论计算机科学电子笔记322(2016)51TC∈TC4传递闭包与可比图检验在本节中,我们提供了对旧算法的新分析,3图的传递闭包:我们将证明其时间复杂度为O(m2logn),其中mtc是传递闭包中的边数因此,我们将3时间复杂度为O(m2logn),时间复杂度为O(m 2 log n)。在相同的时间内,将传递闭包算法与[32]中的结果相结合。问题的定义如下。问题:传输关闭。输入:有向非循环图G=(V,E)。输出:G的传递闭包,即G的最小子图,使得如果存在从顶点v到顶点w的路,则E(v,w)成立。问题:比较 受限制的认知。输入:无向图G。输出:如果G存在传递方向,则为True,否则为False首先,让我们限制在非循环的情况下:如果图不是非循环的,则传递闭包可以很容易地从其强连通分支图的传递闭包推导出来,该分支图是非循环的(更多信息参见[5],第4.3算法1:计算图的传递闭包输入:有向非循环图G=(V,N),存储为外邻居N(v i)对于每个顶点v iV.输出:G的传递闭包GJ=(V,NJ),存储为每个顶点vi∈V的外邻居列表NJ(vi)。1求一个拓扑序(v1,., v n)的V;2 对于i = n到1,3NJ(vi)=N(vi);4对于w在 N(vi)中,5NJ(vi)=NJ(vi)<$NJ(w);6return(V,NJ);算法1提供了算法的伪代码,在[23]中首次发表。该算法的正确性来自于这样一个事实,即顶点是以相反的拓扑顺序进行分析的:当该算法在外部for循环中处理vi时,已经为每个w∈NJ(vi)计算了NJ(w运行时间分析遵循以下定理。定理4.1实现算法1的时间复杂度是可能的3O(m2logn),其中mtc是传递闭包中的边数。证据 算法1中除第5行外的所有步骤最多需要O(m)时间。为M. Borassi等人/理论计算机科学电子笔记322(2016)5165在outw∈V中的OΣΣ(m2)。第5行的分析,我们观察到,如果n out(w)是传递闭包中w的出度,则可以在时间O(|NJ(w)|(|NJ(v i)|))= O(n out(w)log n),如果我们将N J(v i)实现为自平衡二叉搜索树(这些树的计算及其更新对渐近运行时间没有影响)。此外,顶点w在内部for循环中至多被处理n in(w)次,其中n in(w)是w在传递闭包中的入度(实际上,它至多是w在原始图中的入度,甚至是在其传递约简中的入度)。我们得出结论,执行第5行所需的时间最多为(n(w)n(w)logn)。我们主张w∈Vnin(w)nout(w)至多是传递闭包(看作无向图)中三角形的个数。 事实上,如果x是w的内邻居,y是w的外邻居,xy必须是边(图是传递的),xwy形成三角形。在分析不同的顶点时,我们不会将同一个三角形计算两次,因为w总是在拓扑顺序中位于x和y之间。索赔如下。3因为在一个有m条边的图中三角形的个数最多是O(m2)(参见[28]这是一个定理。Q注4.2在分析中,w∈V<$nin (w)nout(w)=O3(m2)紧:如果我们考虑有向无环完全图,时间复杂度O(n)w∈V nin(w)nout(w)=ni=1i(n−3推论4.3可以检验一个图在时间上是否是可传递的,时间复杂度为O(m2logn).证据 为了测试一个图是否是可传递的,我们运行前面的算法,3 3时间复杂度为O(m2logn),如果增加一条边则停止. 时间复杂度为O(m2logn)rithm不停止,mtc必须大于m,并且图是不可传递的。Q推论4.4可以检查一个图在时间上是否是一个可比图.3Σ证据 已知,如果图G是可比较图,则有可能计算G在线性时间内的传递定向[32](对于运行在O(n+mlogn)的更简单算法,请参见[26])。假设H是这个算法的输出,让我们在H上应用前面的推论:如果它是传递的,那么G显然是一个可比图,否则图G不是一个可比图,因为传递定向算法没有提供传递定向。相似性图识别的运行时间与传递闭包算法的运行时间一致,因为所有其他步骤都更快。 这证明了定理。Q最后,我们观察到,我们的传递闭包算法产生一个布尔矩阵乘法算法,运行时间为O(m1。其中m是结果中1的个数,因为计算传递闭包等价于计算布尔矩阵乘法[20]。O m2logn.66M. Borassi等人/理论计算机科学电子笔记322(2016)515结论和未决问题本文分析了二次可解问题的几个困难性结果这项工作可以被视为一个起点,以制定更多的削减,并在其框架内包括几个新的问题。在这些新问题中,包括三个广泛研究的图参数的计算将这些结果与现有的与3SUM问题相关的约简联系起来将是然而,可以将它与其他问题联系起来:例如,已知字符串的局部对齐问题比3SUM更难[3]。另一个开放的问题涉及的计算直径的情况下,平面图和计算半径的图形。 后一种度量类似于直径,但它看起来更问题是,这些问题是否也可以插入到我们的框架中的二次时间困难的问题,或一个真正的次二次算法存在于他们。在其他问题中,不在我们的框架中,但没有真正的次二次时间算法,我们找到了有向图的传递约简的计算(最后,检查一下是否可以在传递闭包算法的运行时删除logn(改进多项式部分也很有趣,但我们认为这要困难得多)。引用[1] Abboud,A.,F. Grandoni和V. V. Williams,Subcubic equivalences between graph centralityproblems,APSP and diameter,第26届ACM/SIAM离散算法研讨会(2015),pp.1681-1697年。[2] Abboud,A.和V.V.Williams,Popular Approaches implement strong lower bounds for dynamicproblems,Proceedings of the 55th Annual Symposium on Foundations of Computer Science(FOCS)(2014)。[3] Abboud,A.,诉诉Williams和O.Weimann,Consequences of Faster Alignment of Sequences,ICALP(2014).[4] Bader,D.一、S. Kintali,K. Madduri和M. Mihail,Approximating betweenness centrality,第五届网络图算法和模型研讨会(2007)。[5] Bang-Jensen,J.和G. Gutin,“有向图理论、算法和应用”,August,Springer,2008年。[6] 巴兰岛,E. D. Demaine和M. Patrascu,Subquadratic algorithms for 3SUM,Materica50(2008),pp.584-596。[7] Bavelas,A.,任务导向群体中的沟通模式,美国声学学会杂志22(1950),pp。七二五七三○[8] Borassi,M.,P. Crescenzi和M. Habib,Into the Square - On the Complexity of Some Quadratic-TimeSolvable Problems,arXiv(2014)。[9] 布兰德斯大学,A faster algorithm for betweenness centrality,数学社会学杂志25(2001),pp. 163-177。M. Borassi等人/理论计算机科学电子笔记322(2016)5167[10] Bringmann , K. , 为 什 么 遛 狗 需 要 时 间 : 除 非 SETH 失 败 , 否 则 Frechet 距 离 没 有 强 次 二 次 算 法 ,Proceedings of the 55th Annual Symposium on Foundations of Computer Science(FOCS)(2014),pp.661-670。[11] Chepoi ,V.和F. F. Dragan , A Linear-Time Algorithm for Finding a Central Vertex of a ChordalGraph,in:ESA,1994,pp.159比170[12] 切波,维,F. F. 德拉甘湾埃斯特朗,M. Habib和Y. 三角双曲测地空间和图的Va x`es,直径,center和应用ximating树,Proceedings of the twenty . . .(2008),pp. 59比68[13] Cohen,E.,D. Delling,T.Pajor和R.F. Werneck,Computing classic closeness centrality,at scale,in:Proceedings of the Second ACM Conference on Online社交网络,COSN'14(2014),pp. 37-50.[14] 科恩,N.,D. Coudert和A. Lancin,用于计算大规模图的双曲性的精确和近似算法,技术报告[研究报告]RR-8074,INRIA(2012)。[15] 科 恩 , N. , D. Coudert 和 A. Lancin , On computing the Gromov hyperbolicity, ACM Journal ofExperimental Algorithms(2015).[16] Crescenz
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)