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

This paper presents parallel, distributed, and quantum algorithms for single-source shortest paths when edges can have negative integer weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in all these settings to n^o(1) calls to any SSSP algorithm that works on inputs with non-negative integer edge weights (non-negative-weight SSSP) with a virtual source. More specifically, for a directed 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 WSSSP (m, n)n^o(1) work and SSSSP (m, n)n^o(1) span, given access to a non-negative-weight SSSP algorithm with WSSSP (m, n) work and SSSSP (m, n) span in the parallel model, and TSSSP (n, D)n^o(1) rounds, given access to a non-negative-weight SSSP algorithm that takes TSSSP (n, D) rounds in CONGEST, and QSSSP (m, n)n^o(1) quantum edge queries, given access to a non-negative-weight SSSP algorithm that takes QSSSP (m, n) queries in the quantum edge query model. This work builds off the recent result of Bernstein, Nanongkai, Wulff-Nilsen [7], which gives a near-linear time algorithm for negative-weight SSSP in the sequential setting. Using current state-of-the-art non-negative-weight SSSP algorithms yields randomized algorithms for negative-weight SSSP with m¹⁺o⁽¹⁾ work and n¹/2+o⁽¹⁾ span in the parallel model, and (n^2/5D^2/5 + √n + D)n^o(1) rounds in CONGEST, and m^1/2n^1/2+o(1) quantum queries to the adjacency list or n^1.5+o⁽¹⁾ quantum queries to the adjacency matrix. Up to a n^o(1) factor, the parallel and distributed results match the current best upper bounds for reachability [23, 12]. Consequently, any improvement to negative-weight SSSP in these models beyond the n^o(1) factor necessitates an improvement to the current best bounds for reachability. The quantum result matches the lower bound up to an n^o(1) factor [9]. Our main technical contribution is an efficient reduction from computing a low-diameter decomposition (LDD) of directed graphs to computations of non-negative-weight SSSP with a virtual source. Efficiently computing an LDD has heretofore only been known for undirected graphs in both the parallel and distributed models, and been rather unstudied in quantum models. The directed LDD is a crucial step of the sequential algorithm in [7], and we think that its applications to other problems in parallel and distributed models are far from being exhausted. Other ingredients of our results include altering the recursion structure of the scaling algorithm in [7] to surmount difficulties that arise in these models, and also an efficient reduction from computing strongly connected components to computations of SSSP with a virtual source in CONGEST. The latter result answers a question posed in [6] in the negative.