In graph theory, a minimum cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge) whose cut set has the smallest number of edges (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.
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 undirected graphs, though these do not necessarily extend to the directed 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). "Proc. 8th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA)". pp. 324–333.
|chapter=ignored (help) (Also NEC Research Institute Technical Report 96-132, 1996)