Aaron Bernstein, Rutgers University

Abstract

We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(mlog^8(n)log W) time when edge weights are integral, can be negative, and are >= -W. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are ~O((m+n^{1.5})log W) and m^{4/3+o(1)}log W. Near-linear time algorithms were known previously only for the special case of planar directed graphs. Also, independently of our work, the recent breakthrough on min-cost flow [Chen, Kyng, Liu, Peng, Probst-Gutenberg and Sachdeva] implies an algorithm for negative-weight SSSP with running time m^{1+o(1)}. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic O(msqrt{n}log nW) bound from over three decades ago [Gabow and Tarjan SICOMP'89].

See: https://theory.cs.rutgers.edu/theory_seminar