Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights
share
This paper presents parallel and distributed algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in either setting to n^o(1) calls to any SSSP algorithm that works with a virtual source. More specifically, for a graph with m edges, n vertices, undirected hop-diameter D, and polynomially bounded integer edge weights, we show randomized algorithms for negative-weight SSSP with (i) W_SSSP(m,n)n^o(1) work and S_SSSP(m,n)n^o(1) span, given access to an SSSP algorithm with W_SSSP(m,n) work and S_SSSP(m,n) span in the parallel model, (ii) T_SSSP(n,D)n^o(1), given access to an SSSP algorithm that takes T_SSSP(n,D) rounds in 𝖢𝖮𝖭𝖦𝖤𝖲𝖳. This work builds off the recent result of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives a near-linear time algorithm for negative-weight SSSP in the sequential setting. Using current state-of-the-art SSSP algorithms yields randomized algorithms for negative-weight SSSP with (i) m^1+o(1) work and n^1/2+o(1) span in the parallel model, (ii) (n^2/5D^2/5 + √(n) + D)n^o(1) rounds in 𝖢𝖮𝖭𝖦𝖤𝖲𝖳. Our main technical contribution is an efficient reduction for computing a low-diameter decomposition (LDD) of directed graphs to computations of SSSP with a virtual source. Efficiently computing an LDD has heretofore only been known for undirected graphs in both the parallel and distributed models. The LDD is a crucial step of the algorithm in [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], and we think that its applications to other problems in parallel and distributed models are far from being exhausted.
READ FULL TEXT