Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
复制标题
对啤酒花充满希望：新的扳手、保护器和啤酒花的下限
DOI：
10.1109/focs54457.2022.00078
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
M. Parter
中科院分区：
文献类型：
--
作者：
Shimon Kogan;M. Parter
Hopsets和Spectron是基本的图结构，在最短路径计算，分布式通信等方面发挥着关键作用。给定图G的（近精确）跳集是加权边H的（小）子集，当将其添加到图G时，减少了近精确最短路径的跳数（边）。另一方面，跨度和距离bridvers，要求从图中删除许多边，同时近似保持最短路径distances.We提供了一个一般的减少计划，从图跳集到已知的度量压缩计划的spanders，emulators和距离bridvers。因此，我们得到了新的和改进的上界结构，以及新的下界结果的跳集。我们的主要结果包括：·对于n-顶点有向赋权图，我们可以给出$V\times V$中p对的$（1+\n）$-近似距离矩阵1，其边数为$O_{\displaystyle $（n\cdot p^{2/5}+（np）^{2/3}）$。对于$p\geq n^{5/4}$，这与[Abboud and Bodwin，SODA 2018]的最先进的可达性边界和[Bodwin，SODA 2016]的精确距离边界的下限相匹配。·对于n-顶点无向加权图，可以用$\overline{O}_{\displaystyle n^{1+o（1）}+p\cdot n^{o（1）}）$边提供$（1+\cdot）$距离保持。到目前为止，这样的界限只能得到无权图。因此，我们还得到了改进的sourcewise spectrum [Roditty，Thorup and Zwick，ICALP 2005]和具有松弛的spectrum [Chan，Dinitz and Gupta，ESA 2006]。·线性大小的精确跳集允许最坏情况的跳界为$\beta=\Omega（n^{1/3}）$。这甚至适用于无向加权图，改进了$\Omega（n^{1/6}）$下界[Huang and Pettie，SIAM J. Discret.数学2021]。有趣的是，这与最近针对线性定向捷径实现的直径界限相匹配。子图，保持成对距离的乘法延伸（1+$\n $）。更概念上，我们的工作取得了重大进展的诱人的开放问题有关的形式之间的联系跳集和spectrometry，例如，由Elkin和Neiman提出[Bull. EATCS 2020]。
Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph G is a (small) subset of weighted edges H that when added to the graph G reduces the number of hops (edges) of near-exact shortest paths. Spanners and distance preservers, on the other hand, ask for removing many edges from the graph while approximately preserving shortest path distances.We provide a general reduction scheme from graph hopsets to the known metric compression schemes of spanners, emulators and distance preservers. Consequently, we get new and improved upper bound constructions for the latter, as well as, new lower bound results for hopsets. Our main results include:•For n-vertex directed weighted graphs, one can provide $(1+\epsilon)$-approximate distance preservers1 for p pairs in $V\times V$ with $O_{\epsilon}(n\cdot p^{2/5}+(np)^{2/3})$ edges. For $p\geq n^{5/4}$, this matches the state-of-the art bounds for reachability preservers by [Abboud and Bodwin, SODA 2018] and the lower bound for exact-distance preservers by [Bodwin, SODA 2016].•For n-vertex undirected weighted graphs, one can provide $(1+\epsilon)$ distance preserves with $\overline{O}_{\epsilon}(n^{1+o(1)}+p\cdot n^{o(1)})$ edges. So far, such bounds could be obtained only for unweighted graphs. Consequently, we also get improved sourcewise spanners [Roditty, Thorup and Zwick, ICALP 2005] and spanners with slack [Chan, Dinitz and Gupta, ESA 2006].•Exact hopsets of linear size admit a worst-case hopbound of $\beta=\Omega(n^{1/3})$. This holds even for undirected weighted graphs, improving upon the $\Omega(n^{1/6})$ lower bound by [Huang and Pettie, SIAM J. Discret. Math 2021]. Interestingly this matches the recent diameter bound achieved for linear directed shortcuts.1I.e., subgraphs that preserve the pairwise distances up to a multiplicative stretch of (1+$\epsilon$).More conceptually, our work makes a significant progress on the tantalizing open problem concerning the formal connection between hopsets and spanners, e.g., as posed by Elkin and Neiman [Bull. EATCS 2020].
登录
查看更多内容
有向跳跃集和并行近似最短路径的高效构建
DOI：
10.1145/3357713.3384270
发表时间：
2020
期刊：
ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
一般图的线性大小对数拉伸路径报告距离预言机
影响因子：
1.3
作者：
Elkin, Michael;Pettie, Seth
通讯作者：
Pettie, Seth
更好的距离保持器和附加扳手
影响因子：
1.3
作者：
Bodwin, Greg;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska
次线性加法扳手下界的层次结构
DOI：
10.1137/1.9781611974782.36
发表时间：
2017
期刊：
SODA 2017
影响因子：
--
作者：
Abboud, Amir;Bodwin, Greg;Pettie, Seth
通讯作者：
Pettie, Seth
几乎线性功和平方根深度的并行可达性
DOI：
10.1109/focs.2019.00098
发表时间：
2019
期刊：
Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Liu, Yang P.;Jambulapati, Arun;Sidford, Aaron
通讯作者：
Sidford, Aaron