Department of
Applied
Mathematics

Distributed Exact Shortest Paths Algorithm in Sublinear Time

Michael Elkin

Abstract

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 Omega(D + \sqrt{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.

We answer this question in the affirmative, and devise an algorithm that requires O((n \log n)^{5/6}) time, for D = O(\sqrt{n \log n}), and O(D^{1/3} \cdot (n \log n)^{2/3}) time, for larger D. This running time is sublinear in n in almost the entire range of parameters.

We also devise the first 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 first computing** G' itself. We then conduct a Bellman-Ford exploration in G' \cup G'', while computing the required edges of G' **on the fly**. As a result, our algorithm computes **exactly** those edges of G' that it really needs, rather than computing approximately the entire G'.

The talk will be self-contained. It is based on a paper that was presented in STOC'17.