For fixed @math , we consider the task of adding to a graph @math a set of weighted shortcut edges on the same vertex set, such that the length of a shortest @math -hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in @math . A set of shortcut edges with this property is called an exact @math -hopset and may be applied in processing distance queries on graph @math . In particular, a @math -hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on @math -hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that @math -hopsets require exponentially fewer shortcuts per node than any previously described distance oracle while incurring only a quadratic increase in the query decoding time, and actually offer a speedup when compared to simple oracles based on a direct application of @math -hopsets. Finally, we consider the problem of computing minimum-size @math -hopset (for any @math ) for a given graph @math , showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When @math , for a given bound on the space used by the distance oracle, we provide a construction of hopsets achieving polylog approximation both for space and query time compared to the optimal @math -hopset oracle given the space bound.
Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the “transitive closure bottleneck,” poses a long-standing open problem. Our main result is an O mn e 0 +s m+n1+ e 0 work polylog-time randomized algorithm that computes paths within (1 + O (1 polylog n ) of shortest from s source nodes to all other nodes in weighted undirected networks with n nodes and m edges (for any fixed e 0 >0). This work bound nearly matches the O d sm sequential time. In contrast, previous polylog-time algorithms required nearly min O d n3 , O d m2 work (even when s =1), and previous near-linear work algorithms required near- O ( n ) time. We also present faster sequential algorithms that provide good approximate distances only between “distant” vertices: We obtain an O m+sn n e 0 time algorithm that computes paths of weight (1+ O (1 polylog n ) dist + O ( w max polylog n ), where dist is the corresponding distance and w max is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse hop sets . A ( d ,e)-hop set of a network G =( V,E ) is a set E * of new weighted edges such that mimimum-weight d -edge paths in V,E∪E* have weight within (1+e) of the respective distances in G . We construct hop sets of size O n1+ e 0 where e= O (1 polylog n ) and d = O (polylog n ).  A (β, e)-hopset for a weighted undirected n-vertex graph G = (V, E) is a set of edges, whose addition to the graph guarantees that every pair of vertices has a path between them that contains at most β edges, whose length is within 1 + e of the shortest path. In her seminal paper, Cohen [8, JACM 2000] introduced the notion of hopsets in the context of parallel computation of approximate shortest paths, and since then it has found numerous applications in various other settings, such as dynamic graph algorithms, distributed computing, and the streaming model. Cohen [8] devised efficient algorithms for constructing hopsets with polylogarithmic in n number of hops. Her constructions remain the state-of-the–art since the publication of her paper in STOC'94, i.e., for more than two decades. In this paper we exhibit the first construction of sparse hopsets with a constant number of hops. We also find efficient algorithms for hopsets in various computational settings, improving the best known constructions. Generally, our hopsets strictly outperform the hopsets of [8], both in terms of their parameters, and in terms of the resources required to construct them. We demonstrate the applicability of our results for the fundamental problem of computing approximate shortest paths from s sources. Our results improve the running time for this problem in the parallel, distributed and streaming models, for a vast range of s. We11A preliminary version appeared in the “Proceedings of the 2nd Israeli Symposium on the Theory of Computing and Systems, 1993.”consider parallel shortest-paths computations in weighted undirected graphsG=(V,E), wheren=|V| andm=|E|. The standardO(n3) work path-doubling (Floyd-Warshall) algorithm consists ofO(logn) phases, where in each phase, for every triplet of vertices (u1,u2,u3)?V3, the distance betweenu1andu3is updated to be no more than the sum of the previous-phase distances between u1,u2 and u2,u3 . We introduce a new NC algorithm that for ?=o(n), considers onlyO(n?2) triplets. Our algorithm performsO(n?2) work and augmentsEwithO(n?) new weighted edges such that between every pair of vertices, there exists a minimum weight path of size (number of edges)O(n ?) (whereO(f)?O(fpolylogn)). To compute shortest-paths, we apply to the augmented graph algorithms that are efficient for small-size shortest paths. We obtain anO(t) timeO(|S|n2+n3 t2) work deterministic PRAM algorithm for computing shortest-paths from |S| sources to all other vertices, wheret?nis a parameter. When the ratio of the largest edge weight and the smallest edge weight isnO(polylogn), the algorithm computes shortest paths. When weights are arbitrary, it computes paths within a factor of 1+n??(polylogn)of shortest. Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say O(n1+Δ) bits. There is an inherent tradeoff between the sparsity parameter Δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when Δ ≥ 1 3 there are schemes with constant additive stretch (distance d is stretched to at most f(d) = d + O(1)), and recent results of Abboud and Bodwin show that when Δ In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function f for sparsity parameter Δ ∈ (0,1 3). Specifically, for any integer k ≥ 2, any compression scheme with size [EQUATION] has a sublinear additive stretch function f: f(d) = d + Ω(d1−1 k). This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's (1 + ϵ, β)-spanners have an essentially optimal tradeoff between Δ, ϵ, and β, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of (1 + ϵ, O(k ϵ)k−1)-spanners with size [EQUATION], where hk Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of (β, ϵ)-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcutting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least 2γ + 1. One consequence is that 's (2010) additive O(γ)-spanners with size [EQUATION] cannot be improved in the exponent. We give parallel algorithms that solve the single-source shortest paths problem on a weighted, undirected graph withnvertices andmedges inO(tlgn) time andO((n3 t2)lgnlg(n t)+mlgn) work, or inO(tlgn) time andO((n3 t3+mn t)lgn) work for anytin the range lgn?t?n. These algorithms run on the EREW PRAM model. They are the first strongly polynomial exact algorithms that run ino(n) time while doingo(n3) work. We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of approximate shortest-path subproblems. Our algorithm for the approximate shortest-path problem is based on the technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search.