Minimum cuts in surface graphs

Joint work with Erin W. Chambers, Jeff Erickson, Amir Nayyeri

SIAM Journal on Computing (SICOMP), 52(1), 156--195, 2023

pdf

Abstract

We describe algorithms to efficiently compute minimum \((s,t)\)-cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph \(G\) with \(n\) vertices embedded on an orientable surface of genus \(g\), our algorithms can solve either problem in \(g^{O(g)} n \log \log n\) or \(2^{O(g)} n \log n\) time, whichever is better. When \(g\) is a constant, our \(g^{O(g)} n \log \log n\) time algorithms match the best running times known for computing minimum cuts in planar graphs.

Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given \(Z_2 \)-homology class, and we give efficient algorithms for this latter problem as well. If \(G\) is embedded on a surface with genus \(g\) and \(b\) boundary components, these algorithms run in \((g + b)^{O(g + b)} n \log \log n\) and \(2^{O(g + b)} n \log n\) time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing it is likely impossible to improve upon the exponential dependencies on \(g\) for this latter problem.

Includes preliminary results from "Global minimum cuts in surface embedded graphs". With Jeff Erickson and Amir Nayyeri in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1309–1318, 2012 along with additional results by the other authors.