# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2303.00811.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ashvinkumar, V., Bernstein, A., Cao, N., Grunau, C., Haeupler, B., Jiang, Y., et al. (2023). Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights. doi:10.48550/arXiv.2303.00811.

Cite as: https://hdl.handle.net/21.11116/0000-000E-3E29-0

##### Abstract

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 $\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.

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.