Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially-bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior point methods (IPMs) and works for general sparse graphs in O(n ^1.5 · poly(logn)) time [Daitch-Spielman, STOC’08]. Intuitively, Ω(n ^1.5) is a natural runtime barrier for IPM-based methods, since they require √n iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested dissection [Lipton-Rose-Tarjan, SINUM’79] and approximate Schur complements [Kyng-Sachdeva, FOCS’16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly √n update time, resulting in a total runtime of O(n · poly(log n)). Our results immediately extend to all families of separable graphs.