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

Preprint · Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin Hao Su

- Archive id: arxiv:2303.00811
- Published: 2023-03-01
- arXiv: https://arxiv.org/abs/2303.00811
- Source URL: https://arxiv.org/abs/2303.00811
- PDF: https://arxiv.org/pdf/2303.00811
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.