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.^[1]

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) that is minimal in some sense. Variations of the minimum cut include:

• The cut with the minimum number of edges among all cuts in an undirected graph, determining the edge connectivity of the graph. Karger's algorithm provides an efficient randomized method for finding this cut.
• The minimum cut problem in undirected weighted graphs can be solved by the Stoer–Wagner algorithm.
• A generalization of the unweighted and undirected minimum cut, the minimum k-cut, in which the goal is to partition the graph into at least k connected components by removing as few edges as possible.
• Graph partition, a family of combinatorial optimization problems in which a graph is to be partitioned into two or more parts with additional constraints such as balancing the sizes of the two sides of the cut.
• The cut in a flow network that separates the source and sink vertices and minimizes the total weight on the edges that are directed from the source side of the cut to the sink side of the cut. As shown in the max-flow min-cut theorem, the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network.
• A cut in a weighted undirected network that separates a particular pair of vertices from each other and has minimum possible weight. A system of cuts that solves this problem for every possible vertex pair can be collected into a structure known as the Gomory–Hu tree of the graph.

Number of minimum cuts

A graph with vertices can at the most have distinct minimum cuts. This bound is tight in the sense that a (simple) cycle on vertices has exactly minimum cuts.

See also

• Maximum cut, a cut that is as large as possible instead of being as small as possible
• Vertex separator, an analogous concept to minimum cuts for vertices instead of edges

References