静5青年讲座 | Deterministic Negative-Weight Shortest Paths...

The textbook Dijkstra's algorithm solves single-source shortest paths in nearly linear time, but only for graphs with non-negative edge weights. For graphs with possibly negative weights, the textbook Bellman–Ford algorithm applies, but it requires quadratic time. Both algorithms are deterministic and were discovered in the 1950s–60s. Since then, people have repeatedly asked whether there exists a deterministic algorithm that achieves both (1) nearly linear time and (2) the ability to handle negative weights. This problem has been actively researched but remained open for more than half a century. In this work, we resolve the problem for graphs with integer weights. We give the first deterministic, nearly-linear-time algorithm for shortest paths in directed graphs with negative edge weights. Before our work, recent years have seen major progress in developing randomized nearly-linear-time algorithms for this problem, but no deterministic algorithm with comparable performance existed, largely due to the inherently randomized component known as low-diameter decomposition. Our main technical contribution is a new structural primitive for directed graphs, called the path cover, which provides a powerful method for deterministically reducing problems on general directed graphs to acyclic ones, and serves as the deterministic analogue of the influential low-diameter decomposition.

Yonggang Jiang is a final-year PhD candidate at the Max Planck Institute for Informatics, advised by Danupon Nanongkai. His research focuses on fast graph algorithms, with an emphasis on derandomization, parallelization, and distributed computing. His work has appeared extensively in top venues such as STOC/FOCS/SODA. He received the SPAA Distinguished Paper Award and is a Google PhD Fellow.