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

For a positive parameter /3, the /3 -bounded distance between a pair of vertices u, v in a weighted undirected graph G = (V,E,o) is the length of the shortest u- v path in G with at most /3 edges, aka hops. For /3 as above and c > 0, a (fl,)-hopset of G = (V,E,o) is a graph GH = (V, H,oH) on the same vertex set, such that all distances in G are (1 + 0 -approximated by fl-bounded distances in G U GH. 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 S2 (n log n) edges, or with a hopbound nu (1). In this paper we devise a construction of linear-size hopsets with hopbound (ignoring the dependence on c) (log log n)1 g log n+0(1) This improves the previous hopbound for linear-size hopsets almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm [11] for computing hopsets with a constant (i.e., independent of n) hopbound requires nu (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 [11]. 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 constant time. All previous constructions of hopsets require either polylogarithmic time per query or polynomial preprocessing time.