Minimum Cuts in Surface Graphs
share
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 loglog n or 2^O(g) n log n time, whichever is better. When g is a constant, our g^O(g) n loglog 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 b boundary components, these algorithms run in (g + b)^O(g + b) n loglog 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.
READ FULL TEXT