For a graph G = (V, E), the problem can be reduced to 2|V| − 2 = O(|V|) maximum flow problems, equivalent to O(|V|) s − t cut problems by the max-flow min-cut theorem. Hao and Orlin have shown an algorithm to compute these max-flow problems in time asymptotically equal to one max-flow computation, requiring O(|V|×|E| log(|V|2/|E|)) steps.
Asymptotically faster algorithms exist for directed graphs, though these do not necessarily extend to the undirected case. A study by Chekuri et al. established experimental results with various algorithms.
- Hao, Jianxiu X.; Orlin, James B. (1994). "A Faster Algorithm for Finding the Minimum Cut in a Directed Graph". Journal of Algorithms 17 (3): 424. doi:10.1006/jagm.1994.1043.
- Chekuri, Chandra S.; Goldberg, Andrew V.; Karger, David R.; Levine, Matthew S.; Stein, Cliff (1997). "Experimental study of minimum cut algorithms". Proc. 8th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). pp. 324–333. (Also NEC Research Institute Technical Report 96-132, 1996)