A Unified Framework for Hopsets and Spanners

Abstract

Given an undirected graph $G=(V,E)$, an {\em $(\hat{I}\pm ,{\hat{I}}^2)$-spanner} $H=(V,E^{\prime })$ is a subgraph that approximately preserves distances; for every $u,v\in V$, $d_H(u,v)\le \hat{I}\pm \cdot d_G(u,v)+{\hat{I}}^2$. An $(\hat{I}\pm ,{\hat{I}}^2)$-hopset is a graph $H=(V,E")$, so that adding its edges to $G$ guarantees every pair has an $\hat{I}\pm$-approximate shortest path that has at most ${\hat{I}}^2$ edges (hops), that is, $d_G(u,v)\le d_{G\cup H}^{({\hat{I}}^2)}(u,v)\le \hat{I}\pm \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 $\hat{I}\pm$. 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^{\hat{I}}\mu ),O(k^{1-\hat{I}\mu }))$-hopset of size $\tilde{O}(n^{1+1/k})$ was shown for any $n$-vertex graph and parameter $0<\hat{I}\mu <1$, and they asked whether this result is best possible. We resolve this open problem, showing that any $(\hat{I}\pm ,{\hat{I}}^2)$-hopset of size $O(n^{1+1/k})$ must have $\hat{I}\pm \cdot {\hat{I}}^2\ge \hat{I}\text{c◯}(k)$.

52 pages, 3 figures