Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

TLDR

Previously, the best dependence on m and n for approximate s‑t flows and cuts was achieved by Goldberg and Rao, giving ~O(m√n ε⁻¹) for flows and ~O(m + n³⁄² ε⁻³) for cuts. The authors introduce a new approach to compute approximately maximum s‑t flows in capacitated, undirected graphs and develop the fastest known algorithms for both approximate maximum flows and minimum cuts. The method computes flows by solving a sequence of electrical flow problems, each given by a Laplacian linear system that can be solved in nearly‑linear time. The resulting algorithms compute a (1‑ε)-approximate maximum s‑t flow in ~O(m n¹⁄³ ε⁻¹⁄³) time and a (1+ε)-approximate minimum s‑t cut in ~O(m + n⁴⁄³ ε⁻¹⁶⁄³) time, surpassing earlier methods.

Abstract

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-ε)-approximately maximum s-t flow in time ~O(mn1/3ε-11/3). A dual version of our approach gives the fastest known algorithm for computing a (1+ε)-approximately minimum s-t cut. It takes ~O(m+n4/3ε-16/3) time. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time ~O({m√nε-1), and approximately minimum s-t cuts in time ~O(m+n3/2ε-3).