b'@online{Bernstein2203.03456,'b"\nTITLE = {Negative-Weight Single-Source Shortest Paths in Near-linear Time},\nAUTHOR = {Bernstein, Aaron and Nanongkai, Danupon and Wulff-Nilsen, Christian},\nLANGUAGE = {eng},\nURL = {https://arxiv.org/abs/2203.03456},\nEPRINT = {2203.03456},\nEPRINTTYPE = {arXiv},\nYEAR = {2023},\nMARGINALMARK = {$\\bullet$},\nABSTRACT = {We present a randomized algorithm that computes single-source shortest paths<br>(SSSP) in $O(m\\log^8(n)\\log W)$ time when edge weights are integral and can be<br>negative. This essentially resolves the classic negative-weight SSSP problem.<br>The previous bounds are $\\tilde O((m+n^{1.5})\\log W)$ [BLNPSSSW FOCS'20] and<br>$m^{4/3+o(1)}\\log W$ [AMV FOCS'20]. Near-linear time algorithms were known<br>previously only for the special case of planar directed graphs [Fakcharoenphol<br>and Rao FOCS'01].<br> In contrast to all recent developments that rely on sophisticated continuous<br>optimization methods and dynamic algorithms, our algorithm is simple: it<br>requires only a simple graph decomposition and elementary combinatorial tools.<br>In fact, ours is the first combinatorial algorithm for negative-weight SSSP to<br>break through the classic $\\tilde O(m\\sqrt{n}\\log W)$ bound from over three<br>decades ago [Gabow and Tarjan SICOMP'89].<br>},\n}\n"