【论文阅读】Reachability and distance queries via 2-hop labels

Cohen E, Halperin E, Kaplan H, et al. Reachability and distance queries via 2-hop labels[J]. SIAM Journal on Computing, 2003, 32(5): 1338-1355.

Abstract

图中的可达性和距离查询是许多应用的基础，从地理导航系统到互联网路由。其中一些应用程序涉及到巨大的图形，但还需要快速的查询回答。我们提出了一种新的数据结构来表示图中的所有距离。数据结构的分布方式是，它可以被视为为顶点分配标签，这样，一个涉及顶点u和v的查询就可以只使用u和v的标签来回答。
我们的标签是基于图中最短路径或所有路径的2跳覆盖。最短路径，这样的封面是一个集合的最短路径，这样每两个顶点u和v，有一个最短路径从u连接两个路径从S我们描述一个算法的几乎最优2跳覆盖一个给定的路径集合。我们的方法是通用的，可以应用于有向或无向图，精确或近似的最短路径，或可达性查询。
我们使用理论和实验方法的结合来研究所提出的数据结构。我们实现了我们的算法，并从不同的应用领域的几个真实网络上检查了结果数据结构的大小。我们的实验表明，标签的总大小通常并不比网络本身大多少，而且通常比网络的传递闭包的显式表示要小得多。

1 Introduction

我们考虑了在有向图或无向图中及时回答距离或可达性查询的问题。我们关注的场景是图/网络明确地给我们，我们能够对它进行一些预处理。生成的数据结构应该相当紧凑，并应该尽可能地加快查询回答的速度。通常，可用于处理查询的计算资源比在预处理阶段可用的计算资源要弱。例如，在地理导航系统中，预处理可以在大型计算机上完成，而查询则使用安装在汽车上的一个弱得多的处理器来回答。
对这个问题有两个幼稚的解决办法。首先是预先计算所有可能的查询的答案，例如，通过求解全对最短路径（APSP）问题，或通过计算网络的传递闭包。然后，就可以在恒定的时间内回答每个查询。然而，这并不是一个可行的选择，特别是对于稀疏网络，因为为n-顶点图产生的数据结构将是大小的（n2）。第二种方法是完全不进行预处理，并回答每个查询，例如，使用单源最短路径（SSSP）计算。这里的空间要求是最小的，但是回答一个在m个边图上的查询可能需要(m)个时间。
本文提出了一种新的处理方案和相应的查询回答算法，用于回答可达性和距离查询。我们的预处理方案生成了一个合理大小的数据结构，即不比原始网络大多少，并且通常比网络的传递闭包的显式表示要小得多。考虑到预先计算的数据结构，我们的查询回答算法可以快速回答距离和可达性查询，比不进行预处理要快得多。
由我们的预处理算法生成的数据结构是分布式的。我们为网络的每个顶点分配了一个距离或可达性标签，这样我们以后就可以只使用这两个顶点的标签来计算两个顶点之间的距离（或可达性关系）。Peleg [10]、加沃耶等人[4]、Thorup和Zwick [12]都考虑了距离标签。然而，所有这些论文都只考虑无向图，并且只考虑最坏情况下的结果。我们主要感兴趣的是有向图，以及在实践中发生的网络上所提出的标记方案的性能。
我们的标签是基于2跳封面的概念。设G = (V；E）是一个（有向或无向）图。对于每一个u；v 2 V，让Puv是G中从u到v的路径的集合（例如，Puv可能是从u到v的所有最短路径的集合）我们没有一个跳是一对（h；u），其中h是G和u 2 V中的路径，跳的手le，是h的端点之一。我们说一个跳H的集合是集合P=的2跳覆盖[uvPuv，如果对于每个u；v 2 V，如果Puv =；，那么有一个路径p 2 Puv和两个跳（h1；u）2 H和（h2；v）2 H，这样p是连接h1h2。我们将展示如何通过将每个跳映射到其处理节点的标签中的一个项目，从这样的封面获得一个2跳标签。
每个这样的项目的性质和标签的解释取决于我们想要解决的问题的规格c变体。例如，考虑无向距离查询。每一组路径Puv包含u和v之间的所有最短路径。u的标签L (u)中对应于跳(h = (u = v0；：：：：vk）的项目为（w (h)；vk），其中w (h)为路径h的权重。两个节点u和v之间的距离可以从它们的标签中得到，通过取两个权值和在L (u)和L (v)中出现的所有节点的最小和的方法。
因此，标签的总大小是jHj（我们在这里计算封面上的跳跃数，而不是它们的总长度）。每个距离/可达性查询都可以及时回答，相应标签的大小是线性的。因此，平均而言，在O（jHj=n）时间内。
我们证明了确定一个最小大小的2跳覆盖（因此，也是一个2跳标记）是一个np困难的问题。然而，我们提出了一个有效的和实用的算法，我们实现了，以获得几乎最优的2跳覆盖。该算法返回的2跳覆盖的大小大于最小可能的2跳覆盖，最多为一个对数因子。在实际应用中，我们期望该算法的性能比率会更好。
我们的算法产生了任何输入图的一个几乎最优的2跳标记。有些图可能有较短的标签，而不是2跳标签。但是，对于许多有趣的图族，如平面图，最优的2跳标记几乎和最优的标记一样短。因此，没有为任何这样的图族设计，我们的算法产生几乎最优的标签。正如我们的实验所述，它也可以很好地工作，例如，主要是平面，或主要是树状，就像许多实际问题一样。
我们推测任何n顶点的m边有向图都有一个2跳覆盖，因此有一个2跳标记，总大小为~O（nm1=2）。我们展示了存在任何距离或可达性标记大小的图（nm1=2）。
我们的方法的一个有用的特性是，通过正确地选择底层路径集，可以为最短路径问题的两个不同变体产生标签：可达性或距离，有向或无向，精确或近似的距离，以及对于顶点对的完整或部分集。尽管所有顶点对的精确有向距离标记是最一般的变体，因为所有其他变体都可以简化为它，但这种区别是重要的，因为约束较少的变体通常享有更紧凑的标记。其中一个例子是有向平面图：可达性或（1 +）近似最短路径的2跳标签大小O（n日志2n）（使用一些轻微的修改构造Thorup [11]）而精确距离，有一个已知的（n4=3）下限任何标签方案[4]。构造允许更紧凑标记的谱c图也不是太难的。因此，应该总是为最小约束的适当变体产生2跳标签。
我们对我们提出的标记方案进行了实验研究。我们使用了几个真实世界的网络，并获得了很有希望的结果，表明所产生的标签的大小通常明显小于显式表示所需要的大小。

2 Reachability and distance queries

设G =（V；E）是一个具有n个= jV j和m个= jEj的加权图（可以是有向的，也可以是m个=jEj）。如果（uv）2E是一条边，我们让w（uv）为附加该边的重量（或成本或长度）。在应用中使用的网络中，附加到边缘的权值是非负的。然而，我们的方法在存在负权重的边缘时也有效。我们设（u；v）为图中从u到v的距离，也就是说，图中从u到v的路径的最小权重，如果有一个存在，否则为1。（我们假设在图中没有负的权值循环，所以所有的距离都是很好的。）
我们希望对图G进行预处理，并得到它的紧凑表示，这样给定一对顶点u；v 2 E，我们就可以快速回答以下查询：
在图中有从u到v的路径吗？
dist (u；v）：图中从u到v的距离是多少？有时，我们会满足（1 +e）近似的距离。
从u发出的哪一条边是从u到v的（最短）路径上的第一条边？
路径（u；v）：在图中找到从u到v的（最短）路径。
可达性查询当然是（定向）距离查询的特殊情况，因为当且仅当从u到v的距离是有限时，才有一个从u到v的路径。如果我们只对可达性性质感兴趣，我们可以假设图中所有边的权值为0。路径查询可以使用重复的第一边查询来回答。在某些情况下，有可能加快处理重复的边缘查询，如果从u最短路径包含，比如，边缘，然后边缘查询的处理时间产生它需要更少的时间然后的一个典型的边缘查询所需的时间。

3 2-hop labels

一个可能的方案实现上述目标如下：在预处理阶段，我们附加到每个顶点u的图一个相对较短的标签L(u)，这样对于任何两个顶点u和v，两个标签L (u)和L (v)将包含足够的信息来回答所需的查询。更正式：
定义3.1。（距离标记）一个加权的、有向的或无向的，图G = (V；E）是一对（L；F），其中L：V！f0；1g和F： f0；1gf0；1g！（IR [ f1g）（E [ f g），对于每个uv2V，如果F（L(u)L(v)=（de），则d=（uv），图中u到v的距离。如果d=为1，则为e=。否则，e是图中从u到v的（最短）路径上的第条边。标记的总位大小为P v2V jL (v)j，其中jL (v)j为L (v)的长度。最大的标签尺寸是自然的maxv2V jL (v)j。如果F（L (v)；L(u)可以在O（jL(u)+（+）+）时间内计算，则假设标记方案具有线性复杂度。
可达性标签也是类似的，和（1 +e）-近似的距离标签是通过要求（u；v）<=d<=（1 +e）（u；v）：我们关注以下形式的可达性/距离标签：
定义3.2。（2跳距离标记）让G =（V；E）是一个加权有向图，G的2跳距离标记给每个顶点v 2 V分配一个标签L (v) =（Lin (v)；Lout (v)），这样Lin (v)是一对的集合（x；（x；v）），其中x 2 V，类似地，Lout (v)是一对的集合（x；（v；x）），其中x 2 V。只要稍微滥用符号，我们也认为Lin (v)和Lout (v)是v的子集，对于任何两个顶点u；v 2 V，我们要求：
（u；v）=最小值x2Lout (u)\Lin (v)（u；x）+（x；v）：
标签的大小被定义为P v2V jLin (v)j + jLout (v)j。
对于近似的距离，我们放宽了对minx2Lout (u)\Lin (v)（u；x）+（x；v）（1 +）（u；v）的要求。
对于无向图，我们可以简化理解：对于每个顶点v，只有一个集合L (v)对（x；(x)），这样对于每个u；v 2 V，我们有（u；v）= minx2L (u)\L (v)（u；x）+（x；v）。标签的大小是P v2V jL (v)j。
一种稍微一般的距离标签如下：
定义3.3。（Steiner2跳距离标签）Steiner2跳距离标签是Lin (v)和Lout (v)分别由形式（x（x(x)和(x)d(x)对组成的标签，其中x 2 X、x(v)d(x)2IR，以及X是任意的夜间集。我们要求
（u；v）=最小x2Lout (u)\Lin (v) d（u；x）+ d（x；v）
（对于无向图和近似距离，也可以得到近似的理解。）
请注意，任何2跳距离标记都是斯坦纳2跳标记，带有X = V和d（x；v）=（x；v）。我们还使用了以下2跳可达性标签的识别。
定义3.4。（2跳可达性标记）设G = (V；E）为有向图。G的2跳可达性标记为每个顶点v 2 V分配一个标签L (v) =（Lin (v)；Lout (v)），这样Lin (v)；Lout (v)V，从每个x 2 Lin (v)到v，从v到每个x 2 Lout (v)。此外，对于任意两个顶点u；v 2 V，我们应该有：
标签的大小被定义为P v2V jLin (v)j + jLout (v)j
2跳斯坦纳可达性标记也是类似，但我们允许Lin (v)和Lout (v)包含来自任意夜间集X的顶点。
在认知3.1中，我们以位为单位测量标签的大小。另一方面，在deniten3.2和3.4中，我们通过它们包含的跳数总数来测量2跳标签的大小。2)我们的2跳标签，如de ned，不支持初始边缘查询。但是，很容易向跳点中添加rst边缘信息，这样它们就可以支持这样的查询。
给定标签L (u) =（Lin (u)；Lout (u)）和L (v) =（Lin (v)；Lout (v)），我们可以很容易地计算（u；v），从+(u)（+）jjLin(v)+)时间。（我们保持Lout (u)和Lin (v)按排序顺序，并合并为它们的交点。）事实上，我们也可以在O（minfjLout(u)j；jLin(v)j）jg)时间中这样做，如果我们为集合Lout (u)和Lin (v)保留哈希表。作为2跳可达性标记的示例，考虑图1中的图和旁边表中显示的2跳标记。我们假设每个顶点v默认都包含在Lin (v)和Lout (v)中。

4 2-hop covers

与2跳标签密切相关的是图中路径集合的2跳覆盖的概念。
定义4.1。（2跳盖）让G = (V；E）是一个图。对于每一个u；v 2 V，让Puv是从u到v的路径的集合（对于无向图，我们有PuvPvu）。让P = fPuv g。我们没有把一个跳变成一对（h；u），其中h是G中的一条路径，u 2 V是h的端点之一。我们把你称为跳跃的手柄。如果每一个=；v 2 V有一个路径，=2，两个=（h1；u）2=和（h2；v）2=，这样= h1h2，即=是h1和h2的连接。封盖的大小为jHj，即H中的跳数。
直观地说，如果p是两个跳点路径的连接，并且跳点的句柄是p的端点，则路径p可以被两个跳点覆盖。通过将带有句柄v的跳映射到节点v标签中的一个项目，我们从2跳覆盖中获得2跳标签。因此，这个标签的大小等于2跳盖的大小。
此外，通过设置Lin (v) = fx j（（x；v）；v）2 Hg和Lout(v)=fxj（（x；x）；v）2 Hg，我们可以从G中所有路径集合的2跳覆盖H中获得可达性标签。反之也适用：从G的可达性标签，我们可以通过向H添加一个相同大小的2跳盖，一个任意路径v；如果x 2 Lout (v)，一个任意路径x组成的跳；如果x 2 Lin (v)，v和端点v。同样地，我们也可以从G中所有最短路径集的2跳覆盖物中获得2跳距离标签，反之亦然。我们还可以从所有近似最短路径集的2跳覆盖中获得近似的距离标签，反之亦然。因此，我们得到了一个最优的所有路径集和所有近似最短路径集的大小分别等于2跳的可达性标签、2跳的距离标签和2跳的近似距离标签。
所有路径的集合、所有最短路径的集合和所有近似最短路径的集合的共同性质，使它们的2跳覆盖对应于2跳标签如下：
定义4.2。（跳不变性）图G =（V；E）中的一组路径P = fPuvg被称为跳不变性，如果存在一个路径集合Q，使
对于任意两个顶点vi和vj，最多有一个路径qij 2 Q，使vi；qijvj。
只要vi；v1vj；p2vk是P的路径，那么qij和qjk存在，qij qjk 2 P存在。
引理4.1。由特定顶点对集合（在有向图或无向图中）之间的所有最短路径组成的集合P是2跳不变的。特别是，所有最短路径的集合都是跳不变的。对于(1 +e（近似最短路径）和所有有向路径的集合。
证明：在所有这些情况下，在Q中放置一条连接每对节点的任意最短路径是最有效的。
定理4.1。在有向图中寻找最短路径集合P的最小2跳覆盖度是一个np困难问题。
证明：我们将3-SAT简化为有向图中最短路径的最小2跳覆盖问题的决策版本。设S是3-SAT的一个实例，其中包含变量x1、x2、x3、：：：、xn和子句C1、C2、3：：、Cm。我们为2跳覆盖问题建立了一个实例。图G由一个枢轴顶点p以及一组可变小工具和子句小工具组成。对应于一个变量x的变量小工具由我们通过添加圆弧（p；bx )和（p；bx )来将pivot p连接到变量小工具。
设C是一个子句C =（X；Y；Z），其中X、Y和Z分别是变量x、y和z的字面意思。对于每个这样的子句C，我们添加一个顶点C和弧(bX；c）、(b Y；c）和(bZ；c）（即，如果X = x我们加弧(bX；c），如果X = x我们加弧(bX；c），同样对于y和z）。
对于每个变量x，我们dePaxiexjj2f1；2g，是从ax i到ex j的有向路径集合。我们也将Ppex j由从p到e x j，j 2 f1的有向路径组成；2g。我们称集合Pax i ex j和Ppex j为对应于变量x的变量路径。对于子句C =（X；Y；Z），我们删除PbX c、PbY c和PbZ c，分别为包含从bX到c、从bY到c、从bZ到c的单条边的有向路径的集合。我们还认为Ppc由从p到c的三条有向路径组成。我们认为上面没有提到的所有东西都是空的。
我们声称，当且仅当2跳覆盖实例具有最多5n + 3m大小的解时，3-SAT实例S是可以满足的。
这一主张的证据如下。假设S是可以满足的，设f是一个令人满意的赋值。我们没有一个2跳的封面H如下。对于每个变量x，如果f (x) = 1，我们将跳（（ax1）、ax 1 )、(b)、(b)和(1)和H（=1）、p）、（=）、c）和（=）和H。可以直接检查如果f满足，则H确实是一个覆盖。H的大小为5n + 3m。
对于另一个方向，设H是一个尺寸为5n + 3m的2跳盖。覆盖所有变量Pbxc和Pbxcx和子句C，封面H必须包括3m不同的跳的形式（bX；c），对于每个条款C和文字X 2 C覆盖对应x的变量路径我们需要至少5跳组成的弧与变量设备的顶点对应x，和p。由于H是一个大小为5n+ 3m的2跳覆盖，我们覆盖每个变量的可变路径。很容易检查覆盖5跳的可变路径的唯一方法是包括H中的跳点（ax1、bx )、（ax2、bx )、ax 2 )、（p、bx )、p）、（bx、ex 1 )、ex 1 )和（bx、ex 2 )、ex 2 )或（ax2）、（ax2）、（bx、ex 1 )、ex 2 )、ex2）=1，当且仅当前一组跳点在H中。由于H也覆盖所有子句C的Ppc，因此S必须是令人满意的真实分配。
然而，如果路径P的集合是跳不变的，我们就可以单独得到一个几乎最优的2跳覆盖。
定理4.2。设G =（V；E）是一个具有jV j =的图，设P是G中的一个跳不变路径集。然后，有一个算法来确定一个2跳覆盖的P，其大小大于最小的覆盖最多一个O（log n）因子。
在证明这个定理之前，我们先介绍一下一些符号。如前一样，让Puv，对于u；v 2 V，是P从u开始，到v结束的路径。设BuvV是出现在来自Puv的路径上的顶点集。（请注意，u；v 2 Buv，如果是Puv =。）一个重新研究的结果表明，对于u；v2v，P的最小2跳覆盖度的大小仅取决于集合Buv。我们还需要讨论最密集的子图问题，并陈述一些已知的结果。
定义4.3。（最密度子图）最密集的子图问题如下：给定一个无向图G =（V；E）和一个子集的子图的平均度是最大化的，即一个使jE(S)=jSj最大化的集合，其中E (S)是连接S的两个顶点的边的集合。
利用flow技术可以在多项式时间内精确地求解最密集的子图问题。Lawler [8，第4章]给出了这样一种算法。由于加洛、格里戈里亚迪斯和Tarjan [3]，目前该问题的最佳可用时间限制是O（mnlog（n2=mn））。将最密集子图问题简化为参数最小割问题，然后利用参数极大割算法的运行时间与戈德堡算法的运行时间相同，和Tarjan [5]算法的非参数极大割算法进行求解。
更实际的兴趣的是针对最密集子图问题的一个更简单的线性时间2-逼近算法，它是对Kortsarz和Peleg [7]提到的算法的一个轻微的修改。根据计算算法迭代地从图中删除一个最小度的顶点。这将生成原始图的n个子图的序列。该算法返回这些子图中最密集的一个。不是迪崇拜检查这个算法可以实现运行在线性时间，这是一个2-近似算法最密集的子图问题，也就是说，平均度子图返回至少一半的平均度最密集的子图。
我们现在可以给出定理4.2的一个证明。
证明：（根据定理4.2），我们将P的一个最小2跳覆盖的问题转换为一个最小集覆盖问题。然后，我们应用贪婪算法和一个覆盖，最多大于一个对数因子（Chvatal[1]，约翰逊[6]，Lovasz[9]）。产生的一个结果是产生的集合覆盖实例是巨大的。然而，我们证明，可以将贪婪算法应用到这个集合覆盖实例，而不显式地生成它。
我们首先回顾了集合覆盖问题的贪婪算法的行。集合覆盖问题的实例是一个地面集T，和一个T的子集的集合S。对于每个S 2 S，都有一个关联的权重w (S)。目标是建立一个子集US，使[S2U S = T和P S2U w（Si）最小化。针对该问题的贪心算法如下。我们维护未覆盖元素t0的集合，它被初始化为T 0 = T。在算法的每次迭代中，我们在U中添加一个集合S，它使jS\T 0 j w (S)的比率最大化。我们迭代到T 0 =。
与2跳覆盖实例对应的集合覆盖实例构造如下。要覆盖的元素的地面集合是T = f（u；v）j==g。对于每个顶点w 2 V和两个子集连接；CoutV，我们有一个集合

附加到这个集合上的权重是jCinj + jCoutj。顶点w被称为集合S的中心（Cin；w；Cout）。目标是建立一个覆盖T的最小总重量集合的集合。（请注意，集合集合的大小是指数级的。）
该集合覆盖实例等同于2跳覆盖问题的证明如下：如果H是一个最小尺寸的2跳定向覆盖，我们让Cin (w) = fuj（（u；w）；u）2 Hg和Cout(w)=fuj（w；u）；u) 2 Hg。然后，我们可以使用w 2 V的集合S（Cin(w)；w；Cout (w)）来覆盖集合T。
相反地，我们首先声称，我们可以假设为w.l.o.g.最小覆盖度最多包含一个具有给定中心的集合。如果盖包含具有相同中心的两组，即S (C0 in；w；C0输出）和S (C00 in；w；C00输出），则可以由组S (C0输入[ C00输入；C0输出[ C00输出）替换。
因此，设S（Cin(w)；w；Cout (w)）为与w 2 V对应的集合。现在可以通过以下方式设置相应的2跳盖：（(u)u）当且仅当u 2 Cin (w)和（（wu）u）2H当且仅当u 2 Cout (w)。
接下来我们必须证明我们可以将贪婪算法应用于这个指数大小集覆盖实例。设t0是T中仍然未被发现的部分。最初是T 0 T。在贪心算法的每一步中，我们都应该得到一个具有最佳比率jS\T 0 j w (S)的集合S。在有向情况下，我们寻找一个集合S（Cin；w；Cout）的比率

是最大化的。
为了做到这一点，我们，对于每一个w 2 V，集合S (w)在所有集合S（Cin；w；Cout）上最大化上述比率，其中w是它们的中心。我们构造了一个辅助的无向二部图Gw =（Vw；Ew），我们称之为w的中心图。顶点集vw包含两个顶点的每个顶点v的原始图g和vout。我们有无向边（uout）2Ew当且仅当（u；v）2 T 0和w 2 Buv。Gw中的许多顶点可能是孤立的，因此可以从图中删除。直接证明了最大化jS（Cout）\T0j=（jCinj+jCoutj=）的问题恰恰是确定Gw最密集子图的问题。
我们解决了这个问题，计算每个中心w 2 V的S (w)，然后选择S (w)具有最佳比率的顶点w。然后，我们将相应的集合S (w)添加到封面上，更新t0，并重复，直到t0为空。
由约翰逊[6]，Lovasz[9]和Chvatal[1]表明，贪婪启发式对集合覆盖问题的性能比率为Ht，其中t是被覆盖的元素数，Ht是调和数。对于我们的问题，元素的数量等于顶点对的数量，这样在它们之间至少有一条路径。因此，我们得到了一个近似的比值

这种构造对无向路径略有不同。要覆盖的集合T是一组（无序的）顶点对fu；vg，使Buv =；。对于每个顶点w 2 V和一个子集CV，我们有一个集合S（C；w）= f fu；vg j u 2 C；v 2 C；w 2 Buv g。证明该集合覆盖问题与我们原来的2跳覆盖问题是等价的，本质上是对于有向情况：设S（C(w)；w）为w then（（u；w）；w）2 H i u 2 C (w)对应的集合。为了解决集合覆盖实例，我们感兴趣的是S (C；w），它可以最大化jS（C；w）\T0jjCj。我们再次首先为每个w分别解决这个最大化问题。这里的辅助图Gw =（V；Ew）包含V的每个顶点的一个副本，通常不是二部图的。我们有边（uv）2Ew当且仅当（uv）2T0和w2Buw。类似地，最大化jS(w)（C；w）的集合S(w)=jCj的问题就是确定Gw最密集子图的问题。
我们的逼近算法与Kortsarz和Peleg [7]给出的关于2-扳手问题的逼近算法有相似的成分。
图2：一个路径的2跳点覆盖物。弹跳是虚线或原始边。菱形表示哪个端点是跳的端点。

4.1 A simple example

为了更好地可视化我们的算法的工作原理，我们演示了它在一种特殊情况下的操作，其中输入是一个由单个有向路径组成的图。我们用连续的整数（1；2；3；：：：：；n）来命名路径上的节点。考虑顶点j的中心图Gj。对于每一个i，k，这样的i < j和k > j在Gj中有一条从iout到亲属的边，它对应于从i到k经过j的路径。由x跳l；j引起的诱导子图的密度使l < j和y跳j；l使l > j是xx+y。对于x和y，它们的和最多为n。
注意，如果我们考虑相应的2跳标签，那么一个节点的最大标签（该节点构成标记端点的跳数）是O（log n）。请注意，即使算法倾向于选择较大的中心图，相应的标签也只存储在\外部的“节点”上。因此，它往往在最大标签度量上也表现良好。
该算法在树上的工作原理类似，迭代地选择子树的重心作为一个中心。因此，生成标签大小为O（n log n）的最大标签大小为O（log n）的标记，我们的算法实际上产生了最佳跳标签。

4.2 Speci c graph families

我们已经看到，我们的算法为所有树（对于问题的任何变体）生成大小为O（n log n）的2跳标记。这与任何树标记的位大小的（n log2 n）的下界相匹配，由于加瓦耶等人[4]。
其他一些图族已知具有紧凑的2跳标记：具有大小为O（n）的分隔符分解的图具有大小为O（n1+log n）的2跳标签（例如，参见[2]）。小分隔符图的最优2跳标记可能是o（n1+log n）。（如果我们的猜想5.1是真的，情况就就是这样。）
对于平面图，Thorup [11]表明O（n log n）大小的可达性和近似的距离标签是可能的。根据他的构造，有相应的大小为O（n log2 n）的2跳标签。我们没有发现2跃可达性标记的匹配下界，因此，对于平面图，有可能存在大小为O（n log n）的最优2跃可达性标记。Thorup的结果特别有趣，因为在平面图的精确距离标签上有一个（n4=3）的下界。
另一个特殊的家族由有界度+的图组成，对于每一对顶点，它们之间至少有一条路径，长度最多为==logdn+（logd+）边。例如，一个随机d正则图具有高概率的性质。对于这样的图，我们可以通过选择每两个节点的跳（（v；u）；v）和（（v；u；u）；u）得到大小为O（n1：5+）的2跳标签，这样最多有一个dD=2e边从v到u的路径。观察总跳数为O（ndD=2）=O（n3=2+）。

5 Lower bounds on reachability and distance labelings

在本节中，我们证明了有向图中可达性标签和2跳可达性标签大小的下界。我们证明的界也适用于有向图和无向图中的距离标记，并且可以直接推广这些情况下的证明。我们从下面简单的引理开始，它给出了任何可达性标记的大小（不一定是2跳可达性标记）的下界。
引理5.1。任何可达性标记方案都必须分配一些总大小（m log（n2 =m））位的n顶点m边图可达性标签。
证明：考虑顶点集合V = f1上的所有有向m边图；2；：：：；ng，其中所有边都从V1 = f1；2；：：：；n=2g到V2 = fn=2 + 1；n=2 + 2；：：：；ng。（假设n为偶数。）有
请注意，引理5.1证明中考虑的图族中的每个图都可以被分配总大小为O（m log n）位的2跳可达性标签。我们简单地让Lout(v)=fu2V2j(v)2Eg对于每个v 2 V1，Lin (v) = fvg为每个v 2 V2，所有其他集合都是空的。因此，2跳可达性标签对于这类图几乎是最优的。下面的推论总结了这一讨论，并表明2跳标签在以下意义上几乎是最优的。
推论5.1。设g (n；L）为大小为L (L log n位）的2跳标签（距离或可达性）的n个节点图的集合。然后，任何通用的标记方案都会在g (n；L）上分配最大大小（L log（n2 =m））位的标签。
证明：考虑在引理5.1的证明中所考虑的图族，其中有n个节点和L条=m条边。这些图有大小为l的2跳标签。推论遵循引理的证明。
接下来，我们使用引理5.1来获得可达性标签的总大小的一个更强的下界。
定理5.1。任何可达性标记方案都必须分配给一些具有n个顶点和m个边边（nm1=2）位的图。9
证明：考虑以下形式的图：从顶点集V1和V2上的二部图开始，其中jV1j=jV2j=m1=2，m=2有向边从V1到V2。接下来，使V1的每个顶点成为带有n=m1=2叶子的星的中心。所有这些叶子都是不相交的，这些叶子的边都指向V1的顶点。同样地，使V2的每个顶点成为带有n=m1=2叶子的星的中心。这一次的边缘被指向远离V2的顶点。此图中的顶点总数为2m1=2n=m1=2+2m1=2=2（n+m1=2）=(n)，边数为2m1=2n=m1=2 + m=2 = m=2 + 2n = (m)。（注意，nmn2，因此，m1=2n。）
设Ui，对于1=m1=2，是由每颗星的第i叶组成的集合。对于每一个i，限制于Ui的可达性关系与集合v1上的可达性关系是同构的[v2]。从引理5.1可以得出，对于至少一个这样的图，我们需要总大小至少为(m)位的可达性标签。因此，附加到所有顶点上的标签的总大小必须至少为（n=m1=2m）=（nm1=2）位。
我们的下一个引理将允许我们在2跳可达性标记的大小上得到一个比定理5.1中的一个稍微更好的下界。该引理建立了一组路径的最优2跳覆盖层大小的下界。为了指定这个引理，我们需要以下定义。给定一个路径和v2v的集合P，我们将hv (w)是通过P中的路径从v到达的顶点数。我们也将hv (w)是通过P路径到达v的顶点的数量。形式上，hv (w) = jfu j w 2 Bvugj，和hv (w) = jfu j w 2 Buvgj。对于每一对节点（；），我们没有覆盖的能力

引理5.2。为任何一个2跳的覆盖

证明：任何一对（a；b）最终被2跳覆盖。其中一个跳数最多参与e（a；b）路径。因此，如果每个跳的成本在它所覆盖的对之间划分，（a；b）的份额至少为1=e (a；b）。因此，跳数的总数至少为P ab 1=e（a；b）。
对于2跳可达性标签，我们可以得到比定理5.1中的界略强的下界。在定理5.1中，（nm1=2）的下界是标签的位的大小，是否在下面的定理中，下界是2跳标签的总跳数。
定理5.2。存在n个顶点的m边图，任何2跳可达性标记方案的总大小必须为（nm1=2）。
证明：我们所考虑的图是在定理5.1的证明中所使用的图的一个子集。我们从jV1j = jV2j = m1=2的完全二部图开始。和前面一样，我们把V1和V2的每个顶点作为一个有n=m1=2叶子的恒星的中心。下面使用引理5.2进行证明。
最后，我们展示了一些具有较大的2跳可达性标签的图具有更短的斯坦纳标签。
推论5.2。存在一组大小为O (n)的Steiner可达性标签的图，其中最合适的2跃可达性标签的大小为（nm1=2）。
证明：定理5.2的证明中的图可以看作是4层图，当且仅当u的层低于v的层时，才可以从u得到v。我们使用集合X=fx1；2；x1；3；x1；4；x2；3；x2；4；4gxi；j将i层所有v放在Lout (v)中，j层所有v放在Lin (v)中。
一个类似的，稍微涉及一些的结构，可以用来生成O(n)结构的无定向均匀加权版本大小的Steiner标签：
推论5.3。存在一组大小为O (n)的无向图，其中最合适的2跳距离标签大小为（nm1=2）。
我们推测定理5.2中给出的界是最可能的：
猜想5.1。设G =（V；E）是一个具有jV j = n和jEj = m的有向图，设P是G中al l最短路径的集合，然后有一个大小为O（nm1=2）的2跳覆盖。

6 The Pairs-Cover problem

定理4.2证明中的算法适用于以下更一般的问题：
问题6.1问题。（对盖）输入：P1Pk，其中每个Pi是一组对或三组整数。输出：一组最小大小的整数对，这样对于每一个i = 1以下内容：
存在一个三重（cj）2Pi，使（ci）2H和（cj）2H，或
存在一对（ci）2Pi，使（ci）2H。
计算跳不变路径集P的2跳覆盖的问题可以映射到以下对覆盖实例：让V = fv0；：：：；j在对覆盖实例中映射到另二P。
对于Pvivj中某个路径上的内部节点的每个vc，我们将以下对/三元组附加到相应的P中：（对于无向图或有向图，映射略有不同）
对于有向路径：我们在P中包括三重（c；n + i；j）和对（i；j）和（j；n + i）。
对于无向路径：我们包括P中的三重（c；i；j）和对（i；j）和（j；i）。
我们对对覆盖实例的输出H解释如下：如果（c；i）2H（i<），则将跳（vc；vi)；vc)放置在盖中。(回想一下，由于P是跳不变的，所以跳可以是指定的通过他们的端点。)对于无向实例，跳变包含无向路径。对于有向实例，跳点包含有向路径。我们也可以有一对（c；i）2 H和（n）在这种情况下我们重新写（+）2+。在这种情况下，我们将跳（+）、vc)放在盖子上。
我们现在提到这个框架所涵盖的另一个自然问题。我们首先考虑2跳盖问题的一个变体，其中跳跃没有句柄。因此，每一跳都仅仅是一条路径，而Puv则是如果有P 2 Puv和两条路径h1；h2 2 H，使P = h1h2。请注意，任何带有手柄的解决方案都可以通过省略手柄转换为没有手柄的解决方案。相反，和通过引入两个端点作为句点的两个跳点，没有句柄的解决方案可以转换为有句柄的解决方案。因此，得到了与手柄有关的变体的最优解Es最多是没有句柄的变体的两倍。因此，我们的贪婪算法可以应用于没有句柄的版本，尽管在近似比中损失了另一个因素2。奇怪的是，似乎没有对贪婪算法的自然修改，为没有句柄的变量得到相同的近似比。
有手柄的变体有更好的标记应用程序，因为有把手的2跳盖和2跳标签之间有1-1个对应关系，但是没有手柄的变体可以有应用程序。
这样一个可能的应用程序是以下问题
问题第6.2节中。（最小2跳表示）设P是字符串的任意集合。P的最小2跳表示是一组子字符串H，这样每个字符串s 2 P都是一个连接两个串的= h1h2。

7 Implementation

我们的实现分两个阶段计算封面。第一阶段不不同应用（即可达性，近似或精确，有向或无向距离），并产生一个成对覆盖问题的实例。第二阶段是针对成对覆盖问题的近似算法。

图3：这是一个构造图上有向最短路径问题的一个实例的成对覆盖实例和中心图的示例。图中有7个节点，分别标记为fa；b；c; d; e; f ; gg.这些图中的夜间距离由7对距离为1的有序对和8对距离为2的有序对组成。相应的对覆盖实例有一组对/三元组的fo到达这15个有序的节点对。表中显示了一些条目；其他条目是对称的：长度为2的所有最短路径的Pxy条目d与Pad对称；Pbg和Pcg与Pag对称；Pge和Pgf与Pgd对称。该图显示了中心g的中心图。在这个中心g中有6个节点raph，对应于有序对的最短路径；gf g。在成对覆盖实例中，这些跳数用a出、b出、c出、d出、ein和fin表示。的边缘中心图是有序对，其中两个跳构成最短路径；同样地，如果三重（gx出，yin）(或（gy出，x出）相同，xy标记一条边s-cover实例。自循环对应于由单个跳点组成的路径。通过选择所有节点，得到了这个特定中心图的最密集子图；这个子图因此涵盖了14个最短路径使用6跳。请注意，Pcf（从c到f的路径）没有被这个中心图覆盖，因为没有穿过节点g的最短路径。这条路径可以通过一个s来覆盖在c的中心图或中心图关闭中的ingle跳（具有自循环的单个节点）。在这种情况下，最小的2跳覆盖物由7跳组成。
第二个阶段然后构建一个中心图的数据结构：对于在某些三组中作为第一个坐标出现的每个数字，我们将一个中心关联起来。对于每个中心c，我们构造一个(u中心图。当且仅当输入中存在一对（c；i）或三重形式（c；；i)或（c；i；）时，c的中心图中存在一个节点i。对于每个三重（cij）都有一个c的中心图中的边缘（i、j）。对于每一对（c；i），在中心图c中的节点i上有一个自循环。图3提供了一个构造中心图的例子。
该算法通过迭代进行，每次迭代的基本操作是子图选择：我们选择一个中心图，并选择剩余节点的子集事件剩余的边缘。选定的节点将被删除。所选的子图实际上是这个中心图中的一个（近似的）最密集的子图。我们实现的近似最密集的子图(ADS)在中心图的大小（边和节点的数量）上是线性的：节点按剩余度（最初使用桶排序）进行排序，每条边被一次查看。
每个输入集P\负责“位于两个中心图中的许多边（每条这样的边对应P`中的三重或一对）”。在我们的数据结构中，所有这些边都是链接的(通过doub的链接列表)。一旦选择了其中的一条边，集合P就被认为是被覆盖的，并且所有这些链接的边都被从它们各自的中心图中移除。因此，子图的选择在一个中心-图可能导致删除其他中心图上的边。
主循环引导中心图的选择，从中选择一个子图。中心被堆地维护。中心c的键是最大的边与节点的比率中心图Gc的精确计算的ADS。堆通过在每个中心图中的ADS计算进行初始化。主循环重复以下步骤，直到所有路径都被覆盖(所有中心图的e桥被移除）：
从堆中删除最大键的中心c。
如果自执行上次ADS计算以来从中心图Gc中删除边，则重新计算ADS，c用一个新的键放在堆中。
否则，如果中心图形未被触及，则选择ADS。如果未选择的边保留在Gc中，则计算一个新的ADS，并使用一个新键将c插入到堆中。
为了使这个实现能够正确地工作，在每一步中选择一个（近似）最小键的中心是很重要的。要看到这一点，请注意一个中心图的键(边的比率与最密集子图中的节点)只有在从图中删除边时才能减少。
我们实现了贪婪集覆盖算法的定理4.2中的证明：算法选择了几个对应于sa的子集ME中心：S (C1、w）、S (C2、w）、：：：S (Ck、w），与剩余子集S (C、w）的比率更新为

（而不是jS（C；w）\T0j=jCj。）其中t0是中心图Gw中未覆盖边的集合。这是通过删除已经从中心图中选择的节点来实现的(注意，边只有在选择两个端点时才被删除)。
观察，这个比率的分子可以随着其他中心的选择而减少。分母也可以减少，但只是因为从同一个中心选择了一个子集。即使与一个特定子集相关的比率可能会增加，但很容易看到，它永远不会超过来自同一中心的最近选择的最密集的子图(如果是，那么这个子集与最近最密集的子图相结合，就会产生一个更密集的子图，因此存在矛盾)。因此，一个中心的最密集子图的最大比率是非递增的。当一个中心被放回堆中时，我们会计算出一个新的最密集的子图，因此我们的堆实现仍然可以找到一个具有最大比率的中心。
在我们的数据集上，这个变体比一个子集的比率的分母保持为｜C｜的变体表现得更好。我们证明了最坏情况下的近似比与其他变体相同：
引理7.1。这种变体达到了O（log n）的最坏情况近似比。
证明：对于每一个集合S =（CS；w），设LS是在前几轮算法中已经选择的CS的元素。设Sk是我们的算法所使用的集合，按这个顺序排列。缺点添加了一个元素v第一次被一个集合=覆盖。我们让wv = jCSnLSj jS\T 0 j。请注意

因此，我们可以证明，当是所覆盖的第j个元素时，那么wvjOPTTj：；Ok0是一个最优覆盖的集合，其中每两个集合都有两个不同的中心。显然，Pk0 i=1 jCOi j = OP T。此外，Pk0 i=1 jOi \ T 0 jjT 0 jjT j第一个组Oi，这样

通过对贪心算法的认识，覆盖v的集合S也将满足jS\T 0 j jCSnLSjjTjj

8 Experiments

我们使用两种合成网络和真实网络来评估我们的标记算法。我们的数据集的选择是由我们的标签方案的两个重要应用指导的，即路由和地理导航系统对于地理导航，距离查询可以告诉用户到达所需目的地的时间或距离。第一边查询可用于生成逐匝驱动目录生态系统。
针对在通信网络中传输的数据包的路由表构成了距离标签的另一个应用。该模型是，每个数据包都携带其目标标签和当前路由器通过考虑当前路由器上的标签和目标标签，获得下一跳，如果需要，则获得\距离”。这有点类似于现在的互联网路由的执行方式： each数据包携带其目标ip地址。路由器在其本地路由表中查找ip地址（最长的pre x匹配），以获得下一跳。然而，路由表正在增长在尺寸方面至于网络的结构，它们通常的直径很小。对于as3间图，图的核心具有很高的扩展性，而intra-AS网络可以几乎是平面的。
ISP-net是一个大型骨干ISP（因特网服务提供商）的网络。网络的节点和（有向）边缘对应于路由器和链路。这个特殊的ISP使用OSPF(开放的最短的路由，边权值是链接的OSPF权重。
BGP是由BGP（边界网关协议）路由器发布的（定向）路径集4。网络的节点都是从核心可到达的互联网上的自主系统（AS）。路径s都是广告中的路径。5我们只考虑3个或更多跳的路径，因为通过在每个节点上的边缘信息可以重建更短的路径。
Roads是阿尔卑斯州（美国）的路线图，从老虎普查数据[13]。这个图是无向的，其权值对应于实际的距离。
Grid-k是一个合成网络。底层网络是一个k-k个网格。边缘以曼哈顿的方式指向，偶数和奇数行边指向相反的方向，同样，偶数和奇数列边-边缘指向相反的方向。边缘权值从[1；100]中均匀随机选择的。
表1列出了每个网络的节点数量、边数、从一个路径到另一个路径的节点对的数量，以及标签的总大小（跳数）。补偿对比是对数与标签总大小之比。压缩比随图的大小和结构而变化，在3到19.6之间。一般来说，我们期望对于较大的图，会有更好的比率。特别地，我们的分析表明，对于平面k网格图，标签的总大小为O（k3），而显式表示为（k4），因此比率为至少(k)。
到目前为止，我们考虑了标签的总大小。另一个感兴趣的参数是特定节点的最大标签大小。这个参数对于分布式应用程序尤为重要。这也是相关的，因为实际计算的距离标签的大小是线性的。对于有向图，我们还考虑列表内或外的最大大小节点的t。表2列出了不同网络的平均和最大标签大小。虽然为了最小化总标签大小，我们的算法似乎也在最大标签度量方面也表现良好。
另一个有趣的问题是关于标签的大小对被覆盖路径的数量的依赖性。我们的算法可以被设置为在任何给定的路径部分被覆盖后停止(实际上，即使在这种情况下，也能提供相同的性能保证。)这种依赖性似乎与Zipf相似（例如，20%-25%的跳数覆盖了一半的路径）。

9 Concluding remarks

我们对有向图和无向图引入了简单和自然的距离和可达性标记方案。我们的标签是由图中路径集的2跳覆盖推导出的。我们给出一个eci构造一个2跳覆盖的大小比最小的2跳覆盖大最多O倍（log n）的ent算法。我们推测存在一个尺寸为~O（nm1=2）的2跳覆盖层具有n个顶点和m条边的任意加权有向图中的最短路径集。证明或反驳这一猜想，也许是剩下的最有趣的问题。我们还演示了通过使用地理导航和互联网路由等应用的合成和真实网络的实验分析，我们的方案。文章来源地址https://www.toymoban.com/news/detail-759313.html

到了这里，关于【论文阅读】Reachability and distance queries via 2-hop labels的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！