Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913617266343936 |
|---|---|
| author | Ashvinkumar, Vikrant Bernstein, Aaron Cao, Nairen Grunau, Christoph Haeupler, Bernhard Jiang, Yonggang Nanongkai, Danupon Su, Hsin Hao |
| author_facet | Ashvinkumar, Vikrant Bernstein, Aaron Cao, Nairen Grunau, Christoph Haeupler, Bernhard Jiang, Yonggang Nanongkai, Danupon Su, Hsin Hao |
| contents | This paper presents parallel, distributed and quantum 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 all these 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}$, (iii) $Q_{SSSP}(m,n)n^{o(1)}$ quantum edge queries, given access to a non-negative-weight SSSP algorithm that takes $Q_{SSSP}(m,n)$ queries in the quantum edge query model. 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}$, (iii) $m^{1/2}n^{1/2+o(1)}$ quantum queries to the adjacency list or $n^{1.5+o(1)}$ quantum queries to the adjacency matrix.
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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_00811 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights Ashvinkumar, Vikrant Bernstein, Aaron Cao, Nairen Grunau, Christoph Haeupler, Bernhard Jiang, Yonggang Nanongkai, Danupon Su, Hsin Hao Distributed, Parallel, and Cluster Computing Data Structures and Algorithms This paper presents parallel, distributed and quantum 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 all these 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}$, (iii) $Q_{SSSP}(m,n)n^{o(1)}$ quantum edge queries, given access to a non-negative-weight SSSP algorithm that takes $Q_{SSSP}(m,n)$ queries in the quantum edge query model. 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}$, (iii) $m^{1/2}n^{1/2+o(1)}$ quantum queries to the adjacency list or $n^{1.5+o(1)}$ quantum queries to the adjacency matrix. 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. |
| title | Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2303.00811 |