Exact Distributed SSSP in Directed Graphs in Sublinear Time
The shortest path problem is one of the central problems in distributed computing. For the last few years, substantial progress has been made on the approximate single source shortest paths problem [Nan14, HKN16, EN16, BKKL16], culminating in an Õ(D+√n) algorithm to compute (1+o(1))-approximate shortest paths, where D is the diameter of the graph. Up to polylogarithmic factors, this running time matches the lower bound of [PR99].
The question of exact shortest paths in distributed computing, however, was unresolved for over a decade, until the recent breakthrough of [Elk17] established a sublinear-time algorithm for exact single source shortest paths on undirected graphs. Shortly after, [HNS17] considered the exact all pairs shortest paths problem on directed graphs.
In this paper, we show the first sublinear time single source shortest path algorithm for directed graphs, running in Õ(n3/4D1/4) time. For small values of D, this algorithm improves the $\tilde Õ(n5/6) time algorithm of [Elk17] and also works for directed graphs. Our algorithm extends to the exact s sources shortest path problem, in which we provide the fastest algorithms for reasonably small s and D.
A video recording will be available on the CMU Theory Youtube channel.