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.

Abstract:

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 genusg, with two specified verticessandt, our algorithm computes a maximum (s,t)-flow in in O(g^{8}nlog^{2}nlog^{2}C) time for integer capacities that sum toC. We also present a combinatorial algorithm that runs ing^{O(g)}n^{3/2}arithmetic operations. Except for the special case of planar graphs, for which an O(nlogn)-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 (glogn)^{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).

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Feb 2013