New $(\alpha ,\beta )$ Spanners and Hopsets

Abstract

An $f(d)$-spanner of an unweighted $n$-vertex graph $G=(V,E)$ is a subgraph $H$ satisfying that $dis{t}_H(u,v)$ is at most $f(dis{t}_G(u,v))$ for every $u,v\in V$. We present new spanner constructions that achieve a nearly optimal stretch of $O(\lceil k/d\rceil )$ for any distance value $d\in [1,k^{1-o(1)}]$, and $d\ge k^{1+o(1)}$. We show the following: 1. There exists an $f(d)$-spanner $H\subseteq G$ with $f(d)\le 7k$ for any $d\in [1,\sqrt{k}/2]$ with expected size $O_k(n^{1+1/k})$. This in particular gives $(\alpha ,\beta )$ spanners with $\alpha =O(\sqrt{k})$ and $\beta =O(k)$. 2. For any $\epsilon \in (0,1/2]$, there exists an $(\alpha ,\beta )$-spanner with $\alpha =O(k^{\epsilon })$, $\beta =O_{\epsilon }(k)$ and of expected size $O_k(n^{1+1/k})$. This implies a stretch of $O(\lceil k/d\rceil )$ for any $d\in [\sqrt{k}/2,k^{1-\epsilon }]$, and for every $d\ge k^{1+\epsilon }$. In particular, it provides a constant stretch already for vertex pairs at distance $k^{1+o(1)}$ (improving upon $d=(\log k{)}^{\log k}$ that was known before). Up to the $o(1)$ factor in the exponent, and the constant factor in the stretch, this is the best possible by the girth argument. 3. For any $\epsilon \in (0,1)$ and integer $k\ge 1$, there is a $(3+\epsilon ,\beta )$-spanner with $\beta =O_{\epsilon }(k^{\log (3+8/\epsilon )})$ and $O_{k,\epsilon }(n^{1+1/k})$ edges. We also consider the related graph concept of hopsets introduced by [Cohen, J. ACM '00]. We present a new family of $(\alpha ,\beta )$ hopsets with $\tilde{O}(k\cdot n^{1+1/k})$ edges and $\alpha \cdot \beta =O(k)$. Most notably, we show a construction of $(3+\epsilon ,\beta )$ hopset with ${\tilde{O}}_{k,\epsilon }(n^{1+1/k})$ edges and hop-bound of $\beta =O_{\epsilon }(k^{\log (3+9/\epsilon )})$, improving upon the state-of-the-art hop-bound of $\beta =O(\log k/\epsilon {)}^{\log k}$ by [Elkin-Neiman, '17] and [Huang-Pettie, '17].

Appeared in SODA 2020