We will discuss recent algorithmic advances for fundamental graph problems, including negative-weight shortest paths, maximum flow, and minimum-cost flow. Classical textbook-style algorithms, such as Bellman-Ford and push-relabel, often lead to \(O(mn)\)-type running times. In recent years, however, there has been tremendous progress on these problems, with algorithms now approaching linear time.
There are two major lines of work behind this progress: one based on continuous optimization, especially interior-point methods (IPMs), and another based on combinatorial techniques. This talk will focus on the latter. In particular, I will discuss two recent results that I coauthored:
- the first deterministic near-linear-time algorithm for negative-weight shortest paths;
- the first combinatorial algorithm for minimum-cost flow that is almost-linear time on dense graphs.
A common perspective behind these advances is lift-and-project: lift the problem to a graph with simpler structure, such as an acyclic graph, solve the problem there, and project the solution back to the original graph. I will explain how this viewpoint helps recent developments for path and flow problems, and discuss some open directions.
