A Unified Framework for Hopsets and Spanners
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929666209611776 |
|---|---|
| author | Neiman, Ofer Shabat, Idan |
| author_facet | Neiman, Ofer Shabat, Idan |
| contents | Given an undirected graph $G=(V,E)$, an {\em $(α,β)$-spanner} $H=(V,E')$ is a subgraph that approximately preserves distances; for every $u,v\in V$, $d_H(u,v)\le α\cdot d_G(u,v)+β$. An $(α,β)$-hopset is a graph $H=(V,E")$, so that adding its edges to $G$ guarantees every pair has an $α$-approximate shortest path that has at most $β$ edges (hops), that is, $d_G(u,v)\le d_{G\cup H}^{(β)}(u,v)\le α\cdot d_G(u,v)$. Given the usefulness of spanners and hopsets for fundamental algorithmic tasks, several different algorithms and techniques were developed for their construction, for various regimes of the stretch parameter $α$.
In this work we develop a single algorithm that can attain all state-of-the-art spanners and hopsets for general graphs, by choosing the appropriate input parameters. In fact, in some cases it also improves upon the previous best results. We also show a lower bound on our algorithm.
In \cite{BP20}, given a parameter $k$, a $(O(k^ε),O(k^{1-ε}))$-hopset of size $\tilde{O}(n^{1+1/k})$ was shown for any $n$-vertex graph and parameter $0<ε<1$, and they asked whether this result is best possible. We resolve this open problem, showing that any $(α,β)$-hopset of size $O(n^{1+1/k})$ must have $α\cdot β\geΩ(k)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_09673 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Unified Framework for Hopsets and Spanners Neiman, Ofer Shabat, Idan Data Structures and Algorithms Given an undirected graph $G=(V,E)$, an {\em $(α,β)$-spanner} $H=(V,E')$ is a subgraph that approximately preserves distances; for every $u,v\in V$, $d_H(u,v)\le α\cdot d_G(u,v)+β$. An $(α,β)$-hopset is a graph $H=(V,E")$, so that adding its edges to $G$ guarantees every pair has an $α$-approximate shortest path that has at most $β$ edges (hops), that is, $d_G(u,v)\le d_{G\cup H}^{(β)}(u,v)\le α\cdot d_G(u,v)$. Given the usefulness of spanners and hopsets for fundamental algorithmic tasks, several different algorithms and techniques were developed for their construction, for various regimes of the stretch parameter $α$. In this work we develop a single algorithm that can attain all state-of-the-art spanners and hopsets for general graphs, by choosing the appropriate input parameters. In fact, in some cases it also improves upon the previous best results. We also show a lower bound on our algorithm. In \cite{BP20}, given a parameter $k$, a $(O(k^ε),O(k^{1-ε}))$-hopset of size $\tilde{O}(n^{1+1/k})$ was shown for any $n$-vertex graph and parameter $0<ε<1$, and they asked whether this result is best possible. We resolve this open problem, showing that any $(α,β)$-hopset of size $O(n^{1+1/k})$ must have $α\cdot β\geΩ(k)$. |
| title | A Unified Framework for Hopsets and Spanners |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2108.09673 |