Proceedings of the 25th Annual Symposium on Computational Geometry, 377–385, 2009.

Abstract:

We describe the first algorithm to compute minimum cuts in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genusg, with two specified verticessandt, our algorithm computes a minimum (s,t)-cut ing^{O(g)}nlogntime. Except for the special case of planar graphs, for which O(nlogn)-time algorithms have been known for more than 20 years, the best previous time bounds for finding minimum cuts in embedded graphs follow from algorithms for general sparse graphs. A slight generalization of our minimum-cut algorithm computes a minimum-cost subgraph in everyZ_{2}-homology class. We also prove that finding a minimum-cost subgraph homologous to a single input cycle is NP-hard.

Note:Since this paper appeared, the main result has been improved in two different ways. Amir Nayyeri and I described a simpler algorithm that runs in2^{O(g)}nlogntime [SODA 2011]. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen improved the running time of the original algorithm tog^{O(g)}nlog logn[STOC 2011].

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012