SIAM Journal on Computing 41(6):1605--1634, 2012.
(Special section of invited papers from the 41st Annual ACM Symposium on Theory of Computing)
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 273–282, 2009.
We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a maximum (s,t)-flow in in O(g8n log2n log2C) time for integer capacities that sum to C. We also present a combinatorial algorithm that runs in gO(g)n3/2 arithmetic operations. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our algorithms improve these time bounds by roughly a factor of √n. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.
Note: The final journal version corrects a number of errors in the STOC paper. Most significantly, the STOC paper incorrectly claims that our combinatorial maxflow algorithm runs in time (g log n)O(g). No near-linear-time combinatorial max-flow algorithm for surface graphs is known, even for undirected graphs with uniform capacities on the torus (g=1).