Homology Flows, Cohomology Cuts

We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. 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(g⁷n log²n log²C) time for integer capacities that sum to C. We also present a combinatorial algorithm that runs in g^O(g)n^3/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 &sqr;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 STOC version of the paper incorrectly claims a combinatorial maxflow algorithm that runs in time (g log n)^O(g); the algorithm is correct, but there is an error in the time analysis. We have corrected this error in the full version of the paper.

Homology flows, cohomology cuts