The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in O (n) time, where n is the number of vertices in the input graph G. Peleg and Rubinovich, FOCS'99, showed a lower bound of Ω(D + √ n) for this problem, where D is the hop-diameter of G. Whether or not this problem can be solved in o(n) time when D is relatively small is a major notorious open question. Despite intensive research that yielded near-optimal algorithms for the approximate variant of this problem, no progress was reported for the original problem. In this paper we answer this question in the a rmative. We devise an algorithm that requires O ((n log n) 5/6 ) time, for D = O ( n log n), and O (D 1/3 · (n log n) 2/3 ) time, for larger D. This running time is sublinear in n in almost the entire range of parameters, speci cally, for D = o(n/ log 2 n). We also generalize our result in two directions. One is when edges have bandwidth b ≥ 1, and the other is the s-sources shortest paths problem. For both problems, our algorithm provides bounds that improve upon the previous state-of-the-art in almost the entire range of parameters. In particular, we provide an all-pairs shortest paths algorithm that requires O (n 5/3 · log 2/3 n) time, even for b = 1, for all values of D. We also devise the rst algorithm with non-trivial complexity guarantees for computing exact shortest paths in the multipass semi-streaming model of computation. From the technical viewpoint, our algorithm computes a hopset G of a skeleton graph G of G without rst computing G itself. We then conduct a Bellman-Ford exploration in G ∪ G , while computing the required edges of G on the y. As a result, our algorithm computes exactly those edges of G that it really needs, rather than computing approximately the entire G .
For the exact SSSP problem, no better upper bound than O(n) was known until two years ago when Elkin REF presented an algorithm with a runtime of O(n 2/3 D 1/3 + n 5/6 ).
Distributed exact shortest paths in sublinear time
STOC 2017
Mathematics Computer Science