Parallel approximate undirected shortest paths via low hop emulators

We present a (1 + )-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving poly(log n) depth and m poly(log n) work for n-nodes m-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For (1 + )-approximation, all prior algorithms with poly(log n) depth perform at least Ω(mn c ) work for some constant c > 0. Improving this long-standing upper bound obtained by Cohen (STOC'94) has been open for 25 years. We develop several new tools of independent interest. One of them is a new notion beyond hopsets -low hop emulator -a poly(log n)-approximate emulator graph in which every shortest path has at most O(log log n) hops (edges). Direct applications of the low hop emulators are parallel algorithms for poly(log n)-approximate single source shortest path (SSSP), Bourgain's embedding, metric tree embedding, and low diameter decomposition, all with poly(log n) depth and m poly(log n) work. To boost the approximation ratio to (1 + ), we introduce compressible preconditioners and apply it inside Sherman's framework (SODA'17) to solve the more general problem of uncapacitated minimum cost flow (a.k.a., transshipment problem). Our algorithm computes a (1 + )-approximate uncapacitated minimum cost flow in poly(log n) depth using m poly(log n) work. As a consequence, it also improves the state-of-the-art sequential running time from m • 2 O( √ log n) to m poly(log n).