A Deterministic Parallel APSP Algorithm and its Applications

In this talk we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has $\tilde{O}(nm+(n/d)3)$ work and $\tilde{O}(d)$ depth for any depth parameter $d\in [1,n]$. To the best of our knowledge, such a trade-off has only been previously described for the real-weighted single-source shortest paths problem using randomization [Bringmann et al., ICALP'17]. Moreover, our result improves upon the parallelism of the state-of-the-art randomized parallel algorithm for computing transitive closure, which has $\tilde{O}(nm+n3/d2)$ work and $\tilde{O}(d)$ depth [Ullman and Yannakakis, SIAM J. Comput. '91]. On the way, we also derandomize the state-of-the-art sequential $\tilde{O}(nm)$-time algorithm for computing a shortest negative cycle in a real-weighted digraph [Orlin et al., Discret. Appl. Math. '18]. Additionally, we discuss how our APSP algorithm can be applied to obtain some new efficient planar graph algorithms in both parallel and sequential regimes.