Title: Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory,
Abstract: For a positive parameter $\beta$, the $\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 $\epsilon>0$, a {\em $(\beta,\epsilon)$-hopset}
of $G = (V,E,\omega)$ is a graph $G' =(V,H,\omega_H)$ on the same vertex set,
such that all distances in $G$ are $(1+\epsilon)$-approximated by
$\beta$-bounded distances in $G\cup G'$.
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 $(\log n)^{\log^{(3)}n+O(1)}$. This improves the previous
bound almost 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
exponentially better than the previous one. Moreover, these hopsets are also
significantly sparser than their counterparts from \cite{EN16}.
We use our hopsets to devise a distributed routing scheme that exhibits
near-optimal tradeoff between individual memory requirement
$\tilde{O}(n^{1/k})$ of vertices throughout preprocessing and routing phases of
the algorithm, and stretch $O(k)$, along with a near-optimal construction time
$\approx D + n^{1/2 + 1/k}$, where $D$ is the hop-diameter of the input graph.