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 $\\mathsf{CONGEST}$. 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/5}D^{2/5} + \\sqrt{n} + D)n^{o(1)}$ rounds in

$\\mathsf{CONGEST}$.

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.

},\n}\n"