TY - GEN
T1 - Negative-Weight Single-Source Shortest Paths in Near-linear Time
AU - Bernstein, Aaron
AU - Nanongkai, Danupon
AU - Wulff-Nilsen, Christian
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(m log8 (n) log W) time when edge weights are integral and can be negative.1 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 vn log W) bound from over three decades ago [Gabow and Tarjan SICOMP'89].
AB - We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(m log8 (n) log W) time when edge weights are integral and can be negative.1 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 vn log W) bound from over three decades ago [Gabow and Tarjan SICOMP'89].
KW - analysis of algorithms
KW - graph algorithms
KW - graphs and networks
KW - path and circuit problems
UR - http://www.scopus.com/inward/record.url?scp=85142865130&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85142865130&partnerID=8YFLogxK
U2 - 10.1109/FOCS54457.2022.00063
DO - 10.1109/FOCS54457.2022.00063
M3 - Conference contribution
AN - SCOPUS:85142865130
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 600
EP - 611
BT - Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PB - IEEE Computer Society
T2 - 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Y2 - 31 October 2022 through 3 November 2022
ER -