Written with Kyle Fox* and Amir Nayyeri*
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1309–1318, 2012.
We give a deterministic algorithm to find the minimum cut in a surface-embedded graph in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, our algorithm computes the minimum cut in gO(g)n log log n time, matching the running time of the fastest algorithm known for planar graphs, due to Łącki and Sankowski, for any constant g. Indeed, our algorithm calls Łącki and Sankowski’s recent O(n log log n)-time planar algorithm as a subroutine.
Previously, the best time bounds known for this problem followed from two algorithms for general sparse graphs: a randomized algorithm of Karger that runs in O(n log3n) time and succeeds with high probability, and a deterministic algorithm of Nagamochi and Ibaraki that runs in O(n2 log n) time. We can also achieve a deterministic gO(g)n2log log n time bound by repeatedly applying the best known algorithm for minimum (s,t)-cuts in surface graphs. The bulk of our work focuses on the case where the dual of the minimum cut splits the underlying surface into multiple components with positive genus.
Note: After we submitted the camera-ready version of this paper, we simplified the algorithm considerably. The simpler algorithm is sketched in Kyle's SODA slides; details will appear in the eventual journal version.