Minimum cut

A graph and two of its cuts. The dotted line in red represents a cut with three crossing edges. The dashed line in green represents one of the minimum cuts of this graph, crossing only two edges.
For the theorem linking minimum cut to maximum flow, see Max-flow min-cut theorem.

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[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 |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.[2]

See also

References

  1. ↑ 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.
  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. (Also NEC Research Institute Technical Report 96-132, 1996)