mincuts

Mincuts are a central concept in graph theory describing the smallest total weight of edges whose removal disconnects a graph into two nonempty parts. In a weighted graph, a cut is given by a partition of the vertex set V into two disjoint subsets S and V\S. The cut capacity is the sum of the weights of the edges that cross from S to V\S. In undirected graphs, each crossing edge contributes its weight once; in directed graphs, the capacity is the sum of the weights of edges directed from S to V\S.

There are s-t cuts, which separate a specified source s from a sink t, and global cuts, which minimize over all partitions without fixing endpoints. The minimum s-t cut has capacity equal to the maximum s-t flow, by the max-flow min-cut theorem. In practice, a minimum cut can be found by solving a corresponding max-flow problem and extracting the cut from the residual graph.

Algorithms for min cuts include Ford-Fulkerson, Edmonds-Karp, Dinic, and push-relabel methods for s-t cuts; their performance depends on the graph and capacities. For undirected graphs seeking a global minimum cut, the Stoer–Wagner algorithm runs in O(n^3) time and returns the minimum cut value and a corresponding partition. More generally, Gomory–Hu trees encode all pairwise minimum cuts with n−1 max-flow computations, allowing many min-cut queries from a single structure.

Mincuts have broad applications in network design and reliability, clustering and image segmentation, graph partitioning, and VLSI design. They reflect bottlenecks in a network and, when weights are integers, yield integer cut values.