Near-Additive Spanners and Near-Exact Hopsets, A Unified View

Given an {\em unweighted} undirected graph $G = (V,E)$, and a pair of parameters $ε> 0$, $β= 1,2,\ldots$, a subgraph $G' =(V,H)$, $H \subseteq E$, of $G$ is a {\em $(1+ε,β)$-spanner} (aka, a {\em near-additive spanner}) of $G$ if for every $u,v \in V$, $d_{G'}(u,v) \le (1+ε)d_G(u,v) + β~.$ It was shown in \cite{EP01} that for any $n$-vertex $G$ as above, and any $ε> 0$ and $κ= 1,2,\ldots$, there exists a $(1+ε,β)$-spanner $G'$ with $O_{ε,κ}(n^{1+1/κ})$ edges, with $β= β_{EP} = \left({{\log κ} \over ε}\right)^{\log κ- 2}~.$ This bound remains state-of-the-art, and its dependence on $ε$ (for the case of small $κ$) was shown to be tight in \cite{ABP18}. Given a {\em weighted} undirected graph $G = (V,E,ω)$, and a pair of parameters $ε> 0$, $β= 1,2,\ldots$, a graph $G'= (V,H,ω')$ is a {\em $(1+ε,β)$-hopset} (aka, a {\em near-exact hopset}) of $G$ if for every $u,v \in V$, $d_G(u,v) \le d_{G\cup G'}^{(β)}(u,v) \le (1+ε)d_G(u,v)~,$ where $d_{G\cup G'}^{(β)}(u,v)$ stands for a $β$-(hop)-bounded distance between $u$ and $v$ in the union graph $G \cup G'$. It was shown in \cite{EN16} that for any $n$-vertex $G$ and $ε$ and $κ$ as above, there exists a $(1+ε,β)$-hopset with $\tilde{O}(n^{1+1/κ})$ edges, with $β= β_{EP}$. Not only the two results of \cite{EP01} and \cite{EN16} are strikingly similar, but so are also their proof techniques. Moreover, Thorup-Zwick's later construction of near-additive spanners \cite{TZ06} was also shown in \cite{EN19,HP17} to provide hopsets with analogous (to that of \cite{TZ06}) properties. In this survey we explore this intriguing phenomenon, sketch the basic proof techniques used for these results, and highlight open questions.

No reviews yet.

No comments yet.