2022/03/07 by Aaron Bernstein, Danupon Nanongkai, Bernstein, Aaron +4 · 2 voices · 18 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2203.03456
We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(mlog8(n)log W) time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are O((m+n1.5)log W) [BLNPSSSW FOCS'20] and m4/3+o(1)log W [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. 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(m√(n)log W) bound from over three decades ago [Gabow and Tarjan SICOMP'89].