Closing the Gap Between Directed Hopsets and Shortcut Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911801733545984 |
|---|---|
| author | Bernstein, Aaron Wein, Nicole |
| author_facet | Bernstein, Aaron Wein, Nicole |
| contents | For an n-vertex directed graph $G = (V,E)$, a $β$-\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 $β$ edges. A natural generalization of shortcut sets to distances is a $(β,ε)$-\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+ε)$-approximate shortest path in $G \cup H$ with at most $β$ edges.
There is a large literature on the tradeoff between the size of a shortcut set / hopset and the value of $β$. We highlight the most natural point on this tradeoff: what is the minimum value of $β$, such that for any graph $G$, there exists a $β$-shortcut set (or a $(β,ε)$-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 $β= O(n^{1/2})$, but in a breakthrough result Kogan and Parter [SODA 2022] improve this to $β= \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 $ε$ there is a $(\tilde{O}(n^{1/3}),ε)$ hopset with $O(n)$ edges. More generally, we achieve a smooth tradeoff between hopset size and $β$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_04507 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Closing the Gap Between Directed Hopsets and Shortcut Sets Bernstein, Aaron Wein, Nicole Data Structures and Algorithms For an n-vertex directed graph $G = (V,E)$, a $β$-\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 $β$ edges. A natural generalization of shortcut sets to distances is a $(β,ε)$-\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+ε)$-approximate shortest path in $G \cup H$ with at most $β$ edges. There is a large literature on the tradeoff between the size of a shortcut set / hopset and the value of $β$. We highlight the most natural point on this tradeoff: what is the minimum value of $β$, such that for any graph $G$, there exists a $β$-shortcut set (or a $(β,ε)$-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 $β= O(n^{1/2})$, but in a breakthrough result Kogan and Parter [SODA 2022] improve this to $β= \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 $ε$ there is a $(\tilde{O}(n^{1/3}),ε)$ hopset with $O(n)$ edges. More generally, we achieve a smooth tradeoff between hopset size and $β$ 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. |
| title | Closing the Gap Between Directed Hopsets and Shortcut Sets |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2207.04507 |