Title: Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC.

Author: Michael Elkin and Ofer Neiman 

Abstract: For a positive parameter $\beta$,  the {\em $\beta$-bounded distance} between a pair of vertices $u,v$ in a weighted undirected graph $G = (V,E,\omega)$ is 
the length of the shortest $u-v$ path in $G$ with at most $\beta$ edges, aka {\em  hops}. For $\beta$ as above and $\eps > 0$, a {\em $(\beta,\eps)$-hopset} of 
$G = (V,E,\omega)$ is a graph $G_H =(V,H,\omega_H)$ on the same vertex set, such that all distances in $G$ are $(1+\eps)$-approximated by $\beta$-bounded distances 
in $G \cup G_H$.

Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. 
Currently existing constructions of hopsets  produce hopsets either with $\Omega(n \log n)$ edges, or with a hopbound $n^{\Omega(1)}$. In this paper we devise a 
construction of {\em linear-size} hopsets with hopbound  (ignoring the dependence on $\eps$) $(\log \log n)^{\log \log n + O(1)}$.  This improves the previous hopbound 
for linear-size hopsets almost {\em exponentially}.

We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm \cite{EN16} for computing hopsets with a 
constant (i.e., independent of $n$) hopbound requires $n^{\Omega(1)}$ time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a 
constant hopbound, i.e., our running time is {\em exponentially} better than the previous one.  Moreover, these hopsets are also significantly sparser than their 
counterparts from \cite{EN16}. We apply these hopsets to achieve the following online variant of shortest paths in the PRAM model: preprocess a given weighted graph 
within polylogarithmic time, and then given any query vertex $v$, report all approximate shortest paths from $v$ in {\em constant time}. All previous constructions of 
hopsets require either polylogarithmic time per query or polynomial preprocessing time.