Homology flows, cohomology cuts

Written with Erin Wolf Chambers and Amir Nayyeri*

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 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).


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