Minimum cut

In graph theory, a minimum cut of a graph is a cut whose cutset has the smallest number of elements (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^[1] 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|²/|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.^[2]

Karger's algorithm is the fastest known minimum cut algorithm, is randomized, and computes a minimum cut with high probability in time O(|E| log³|V|).

Example Algorithm

Here is an example of a randomized minimum cut algorithm:

 // find_min_cut(undirected graph G) {
 // while there are more than 2 nodes in G do {
 // pick an edge (u,v) at random in G
 // contract the edge, while preserving multi-edges
 // remove all loops
 // }
 // output the remaining edges
 // }[1]

See also

• Maximum cut
• Minimum k-cut
• Graph partitioning problem
• Pseudo-Boolean function

References

1. ^ Hao, Jianxiu; Orlin, James B. (1994). "A faster algorithm for finding the minimum cut in a directed graph". J. Algorithms 17: 424–446. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.2427. 
2. ^ 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. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5703.