(SSSP) in $O(m\\log^8(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 $\\tilde O((m+n^{1.5})\\log W)$ [BLNPSSSW FOCS'20] and

$m^{4/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 $\\tilde O(m\\sqrt{n}\\log W)$ bound from over three

decades ago [Gabow and Tarjan SICOMP'89].

},\n}\n"