Closing the Gap Between Directed Hopsets and Shortcut Sets
Closing the Gap Between Directed Hopsets and Shortcut Sets
复制标题
缩小定向 Hopsets 和 Shortcut Sets 之间的差距
DOI：
10.48550/arxiv.2207.04507
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Nicole Wein
中科院分区：
文献类型：
--
作者：
A. Bernstein;Nicole Wein
对于n点有向图$G=(V，E)$，$\beta$-emph{捷径集}$H$是一组附加边$H\subseteq V\次V$，使得$G\杯H$具有与$G$相同的传递闭包，并且对于V$中的每一对$u，v\，在$G\杯H$中存在一条至多含有$\beta$边的$UV$-路.最短路径集到距离的自然推广是$(\beta，\epsilon)$-\emph{Hopset}$H\subseteq V\次V$，其中要求$H$和$G\cup H$具有相同的最短路径距离，并且对于V$中的每个$u，v\，在$G\Cup H$中存在$(1+\epsilon)$-近似最短路径，且至多有$\beta$边。有大量文献研究了捷径集/希望集的大小和$\beta$的价值之间的权衡。我们强调了这一权衡中最自然的点：$\beta$的最小值是多少，使得对于任何图$G$，都存在一个具有$O(N)$边的$\beta$-捷径集(或$(\beta，\epsilon)$-Hopset)？这不仅本身是一个自然的结构问题，而且捷径集/希望集构成了许多分布式、并行和动态的可达性/最短路径算法的核心。直到最近，最广为人知的上界是一个民间传说结构，证明了$\beta=O(n^{1/2})$，但在一个突破性的结果中，Kogan和Parter[Soda 2022]将其改进为捷径集的$\beta=\tilde{O}(n^{1/3})$和Hopset的$\tilde{O}(n^{2/5})$。我们的结果是缩小了捷径集和希望集之间的差距。也就是说，对于任何图$G$和任何固定的$\epsilon$，都存在一个具有$O(N)$边的$(\tide{O}(n^{1/3})，\epsilon)$Hopset。更广泛地说，我们在Hopset大小和$\beta$之间实现了平滑的折衷，这与Kogan和Parter对于最短路径集(最高可达PolyLog因子)的权衡完全匹配。使用最近对Kogan和Parter的黑盒简化，我们的新Hopset意味着近似距离保持的界得到了改进。
For an n-vertex directed graph $G = (V,E)$, a $\beta$-\emph{shortcut set} $H$ is a set of additional edges $H \subseteq V \times V$ such that $G \cup H$ has the same transitive closure as $G$, and for every pair $u,v \in V$, there is a $uv$-path in $G \cup H$ with at most $\beta$ edges. A natural generalization of shortcut sets to distances is a $(\beta,\epsilon)$-\emph{hopset} $H \subseteq V \times V$, where the requirement is that $H$ and $G \cup H$ have the same shortest-path distances, and for every $u,v \in V$, there is a $(1+\epsilon)$-approximate shortest path in $G \cup H$ with at most $\beta$ edges. There is a large literature on the tradeoff between the size of a shortcut set / hopset and the value of $\beta$. We highlight the most natural point on this tradeoff: what is the minimum value of $\beta$, such that for any graph $G$, there exists a $\beta$-shortcut set (or a $(\beta,\epsilon)$-hopset) with $O(n)$ edges? Not only is this a natural structural question in its own right, but shortcuts sets / hopsets form the core of many distributed, parallel, and dynamic algorithms for reachability / shortest paths. Until very recently the best known upper bound was a folklore construction showing $\beta = O(n^{1/2})$, but in a breakthrough result Kogan and Parter [SODA 2022] improve this to $\beta = \tilde{O}(n^{1/3})$ for shortcut sets and $\tilde{O}(n^{2/5})$ for hopsets. Our result is to close the gap between shortcut sets and hopsets. That is, we show that for any graph $G$ and any fixed $\epsilon$ there is a $(\tilde{O}(n^{1/3}),\epsilon)$ hopset with $O(n)$ edges. More generally, we achieve a smooth tradeoff between hopset size and $\beta$ which exactly matches the tradeoff of Kogan and Parter for shortcut sets (up to polylog factors). Using a very recent black-box reduction of Kogan and Parter, our new hopset implies improved bounds for approximate distance preservers.
登录
查看更多内容
有向跳跃集和并行近似最短路径的高效构建
DOI：
10.1145/3357713.3384270
发表时间：
2020
期刊：
ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
简短公告：改进的分布式近似单源最短路径算法
DOI：
10.1145/3465084.3467945
发表时间：
2021
期刊：
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
次线性加法扳手下界的层次结构
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