Homology flows, cohomology cuts

Erin W. Chambers, Jeff G Erickson, Amir Nayyeri

Research output: Contribution to journalArticlepeer-review

Abstract

We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given a graph embedded on a surface of genus g, with two specified vertices s and t and integer edge capacities that sum to C, our algorithm computes a maximum (s, 3t)2-flow in O(g8n log2n log2 C) time. We also present a combinatorial algorithm that takes gO(g)n3/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. For graphs of any fixed genus, our algorithms improve these time bounds by roughly a factor of √n. Our key insight is to optimize the homology class of the flow, rather than directly optimizing the flow itself; two flows are in the same homology class if their difference is a weighted sum of directed facial cycles. A dual formulation of our algorithm computes the minimum-cost circulation in a given (real or integer) homology class.

Original languageEnglish (US)
Pages (from-to)1605-1634
Number of pages30
JournalSIAM Journal on Computing
Volume41
Issue number6
DOIs
StatePublished - Dec 31 2012

Keywords

  • Homology
  • Maximum flow
  • Topological graph theory

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Homology flows, cohomology cuts'. Together they form a unique fingerprint.

Cite this