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

Abstract

Given an {\em unweighted} undirected graph $G=(V,E)$, and a pair of parameters $\epsilon >0$, $\beta =1,2,\dots$, a subgraph $G^{\prime }=(V,H)$, $H\subseteq E$, of $G$ is a {\em $(1+\epsilon ,\beta )$-spanner} (aka, a {\em near-additive spanner}) of $G$ if for every $u,v\in V$, $$d_{G^{\prime }}(u,v)\le (1+\epsilon )d_G(u,v)+\beta .$$ It was shown in \cite{EP01} that for any $n$-vertex $G$ as above, and any $\epsilon >0$ and $\kappa =1,2,\dots$, there exists a $(1+\epsilon ,\beta )$-spanner $G^{\prime }$ with $O_{\epsilon ,\kappa }(n^{1+1/\kappa })$ edges, with $$\beta ={\beta }_{EP}={\left(\frac{\log \kappa }{\epsilon }\right)}^{\log \kappa -2}.$$ This bound remains state-of-the-art, and its dependence on $\epsilon$ (for the case of small $\kappa$) was shown to be tight in \cite{ABP18}. Given a {\em weighted} undirected graph $G=(V,E,\omega )$, and a pair of parameters $\epsilon >0$, $\beta =1,2,\dots$, a graph $G^{\prime }=(V,H,{\omega }^{\prime })$ is a {\em $(1+\epsilon ,\beta )$-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^{\prime }}^{(\beta )}(u,v)\le (1+\epsilon )d_G(u,v),$$ where $d_{G\cup G^{\prime }}^{(\beta )}(u,v)$ stands for a $\beta$-(hop)-bounded distance between $u$ and $v$ in the union graph $G\cup G^{\prime }$. It was shown in \cite{EN16} that for any $n$-vertex $G$ and $\epsilon$ and $\kappa$ as above, there exists a $(1+\epsilon ,\beta )$-hopset with $\tilde{O}(n^{1+1/\kappa })$ edges, with $\beta ={\beta }_{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.

arXiv commentA survey

References in corpus (1)

• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

Cited by in corpus (1)

• Additive Sparsification of CSPs