Marek Sokołowski, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP

In this talk, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within $\widetilde{O}(m+n^{2-\varepsilon})$ work and $\widetilde{O}(n^{1-\varepsilon})$ depth for some positive $\varepsilon>0$. For dense graphs with non-negative real weights, this yields the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Moreover, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights.

This is a joint work with Adam Karczmarz and Wojciech Nadara.