Minimum cut
In graph theory, a minimum cut (or min-cut) of a graph is a partition of its vertices into two non-empty disjoint subsets such that the total weight of the edges with endpoints in different subsets—known as the cut's capacity—is minimized.[1] This problem measures the graph's connectivity by identifying the smallest set of edges whose removal disconnects the graph into at least two components.[1] There are two primary variants: the s-t minimum cut, which requires specified vertices s (source) and t (sink) to lie in different subsets of the partition, and the global minimum cut, which imposes no such restriction and seeks the overall smallest cut across any partition. The global variant is typically defined for undirected graphs, while the s-t variant is central to directed flow networks, where edge capacities represent limits on flow; by the max-flow min-cut theorem, the maximum flow value from s to t equals the capacity of the minimum s-t cut.[2][3] This theorem, proved by Ford and Fulkerson in 1956, enables computing s-t min-cuts via maximum flow algorithms such as the Ford-Fulkerson method, which iteratively augments flow along paths until saturation.[3] Minimum cuts have broad applications in computer science and engineering, including image segmentation in computer vision—where they delineate objects from backgrounds by modeling pixel affinities as edge weights—and network reliability analysis, such as identifying vulnerabilities in power grids or transportation systems by simulating edge failures.[1] For global min-cuts, efficient randomized algorithms like Karger's algorithm (1996) contract random edges repeatedly to isolate the cut with high probability, and its improvements achieve near-linear time complexity.[4] Recent advances, including deterministic near-linear time solutions for weighted graphs (as of 2024), continue to improve scalability for large-scale problems in graph partitioning and optimization.[5]Fundamental Concepts
Definition
In graph theory, a cut of a graph G = (V, E) is a partition of the vertex set V into two disjoint nonempty subsets S \subseteq V and T = V \setminus S, such that the cut itself is the set of edges in E that have one endpoint in S and the other in T.[6] This partition separates the vertices into two groups, with the crossing edges forming the boundary between them.[7] The definition varies slightly between undirected and directed graphs. In an undirected graph, where edges have no direction, the cut includes every edge with endpoints in different subsets, reflecting the bidirectional nature of connections.[6] In a directed graph, the cut consists only of edges oriented from S to T, excluding any edges directed from T to S.[8] For illustration, consider an undirected graph with vertices A, B, and C, and edges A-B, B-C, and A-C. The partition S = \{A\} and T = \{B, C\} yields a cut comprising the edges A-B and A-C. The capacity of such a cut, which quantifies its size via edge weights, is addressed separately.[6]Capacity
In graph theory, particularly in the context of flow networks, the capacity of a cut provides a quantitative measure of the "size" of the partition separating the vertex set. For a directed graph G = (V, E) with nonnegative edge capacities w: E \to \mathbb{R}_{\geq 0}, consider a cut defined by a partition of the vertices into two nonempty subsets S \subseteq V and T = V \setminus S. The capacity c(S, T) is the total weight of all directed edges crossing from S to T, formally given by c(S, T) = \sum_{\substack{u \in S, \\ v \in T}} w(u, v). This sum aggregates the capacities of only those edges directed from S to T, ignoring edges within S, within T, or from T to S.[9][10] For an undirected graph G = (V, E) with nonnegative edge capacities w: E \to \mathbb{R}_{\geq 0}, the capacity c(S, T) is the total weight of all edges with one endpoint in S and the other in T, formally given by c(S, T) = \sum_{\substack{u \in S, \\ v \in T \\ \{u,v\} \in E}} w(\{u, v\}). This accounts for the undirected nature of the edges, summing the weights of all crossing edges without regard to direction.[6] Capacities are typically assumed to be nonnegative real numbers, ensuring that the cut capacity is well-defined and finite under standard conditions; zero capacity corresponds to the absence of an edge between the subsets, while infinite capacity may be assigned to edges that are effectively uncuttable, rendering any cut including such an edge to have infinite capacity and thus ineligible as a minimum.[10][11] For illustration, consider a directed graph with vertices \{A, B, C\} and edges A \to B with weight 3, A \to C with weight 1, and B \to C with weight 2. For the partition S = \{A\} and T = \{B, C\}, the crossing edges are A \to B and A \to C, yielding c(S, T) = 3 + 1 = 4.[9]s-t Minimum Cut
Source-Sink Formulation
In the context of flow networks, the source-sink formulation, also known as the s-t cut, specializes the general notion of a cut to scenarios involving designated terminals: a source vertex s and a sink vertex t. A flow network is a directed graph G = (V, E) equipped with non-negative capacity functions c: E \to \mathbb{R}_{\geq 0}, where s \in V serves as the origin of flow and t \in V as its destination. An s-t cut is defined as a partition of the vertex set V into two disjoint subsets S and T such that S \cup T = V, s \in S, and t \in T; the capacity of this cut is the sum of the capacities of all edges directed from S to T, denoted c(S, T) = \sum_{u \in S, v \in T} c(u, v).[12][13] The minimum s-t cut refers to the s-t cut with the smallest capacity among all possible such partitions, representing the minimum total capacity that must be "severed" to disconnect s from t in the network. This formulation is central to analyzing bottlenecks in flow propagation from source to sink, where the cut edges form the boundary across which flow cannot cross without violating the partition. Unlike general cuts without specified terminals, s-t cuts enforce the inclusion of s and t in their respective sets, ensuring relevance to directed flow paths.[14][15] For illustration, consider a simple flow network with vertices s, a, and t, and directed edges s \to a with capacity 1, s \to t with capacity 2, and a \to t with capacity 3. One possible s-t cut is S = \{s\} and T = \{a, t\}, with cut edges s \to a and s \to t, yielding capacity $1 + 2 = 3. Another is S = \{s, a\} and T = \{t\}, with the single cut edge a \to t, yielding capacity 3. In this case, both cuts achieve the minimum capacity of 3, highlighting how multiple partitions may tie for minimality.[13] The source-sink formulation of cuts emerged in the 1950s amid early research on network flows, motivated by applications such as transportation and communication systems during the Cold War era. Seminal work by Lester R. Ford Jr. and Delbert R. Fulkerson in 1956 formalized these concepts within their development of algorithms for maximum flow, establishing s-t cuts as a foundational tool in combinatorial optimization.[16]Properties
The collection of all minimum s-t cuts exhibits a closure property, forming a distributive lattice under the operations of union and intersection. That is, the intersection of any two minimum s-t cuts is itself a minimum s-t cut, and the union of any two is also a minimum s-t cut. This algebraic structure arises from the duality in the max-flow min-cut framework, where the cuts partition the vertices consistently while preserving the minimum capacity.[17][18] A minimum s-t cut is intimately related to the residual graph of a maximum flow. In particular, after computing a maximum flow, a minimum s-t cut corresponds to a partition where there are no augmenting paths from s to t in the residual graph; the source-side set S consists of all vertices reachable from s via residual edges, ensuring no residual capacity crosses from S to T = V \setminus S. This property underpins the correctness of flow-based algorithms for identifying minimum cuts.[17][19] In networks with unit capacities (all edge capacities equal to 1), the minimum s-t cut capacity equals the maximum flow value, which is an integer due to the integral flow theorem. This guarantees that the min-cut value is an integer, simplifying analysis in unweighted or binary capacity settings.[17][20] To illustrate the closure property, consider a simple directed graph with vertices s, a, b, t and edges s \to a (capacity 1), a \to t (capacity 1), s \to b (capacity 1), b \to t (capacity 1). The minimum s-t cut capacity is 2. One minimum s-t cut is S_1 = \{s\}, T_1 = \{a, b, t\}, with capacity 2 from edges s \to a and s \to b. Another is S_2 = \{s, a, b\}, T_2 = \{t\}, with capacity 2 from edges a \to t and b \to t. Their union S_1 \cup S_2 = \{s, a, b\} gives the second cut, capacity 2; their intersection S_1 \cap S_2 = \{s\} gives the first cut, also capacity 2. Thus, both operations yield minimum cuts. This example highlights how multiple minimum cuts can nest, with unions and intersections maintaining the minimum capacity.[17]Global Minimum Cut
Without Specified Terminals
In graph theory, the global minimum cut (or min-cut without specified terminals) of an undirected graph G = (V, E) is defined as a partition of the vertex set V into two non-empty disjoint subsets S and T such that V = S \cup T and S \cap T = \emptyset, minimizing the capacity of the cut, which is the total weight of edges with one endpoint in S and the other in T.[21] This capacity represents the minimum "bottleneck" separating the graph into two components, without designating specific source or sink vertices.[22] Unlike the s-t minimum cut, which requires fixed terminals s \in S and t \in T and is typically formulated for directed graphs, the global minimum cut applies primarily to undirected graphs and considers all possible bipartitions, yielding the smallest such capacity across the entire graph.[21] This formulation captures the intrinsic connectivity of the graph as a whole, independent of particular vertices.[23] A simple example is the cycle graph C_n on n vertices with unit edge weights, where the global minimum cut has capacity 2; any partition separating the vertices into two contiguous segments connected by exactly two edges achieves this minimum.[22] In unweighted graphs, the capacity of the global minimum cut equals the edge connectivity \lambda(G) of the graph, defined as the size (number of edges) of the smallest set of edges whose removal disconnects G. In weighted graphs, it is the minimum weighted capacity.[23] This equivalence highlights its role in measuring the robustness of graph connectivity.[21]Computational Complexity
For the global minimum cut, which lacks specified terminals, one deterministic approach reduces the problem to O(n) invocations of s-t minimum cut computations by fixing an arbitrary source and computing cuts to all possible sinks, then minimizing over these values. This yields a time complexity of O(n \cdot VE^2) using the Edmonds-Karp algorithm, where V is the number of vertices and E is the number of edges. The problem remains solvable in polynomial time, though practical implementations often rely on specialized methods. Randomized algorithms like Karger's algorithm provide faster practical solutions, with the improved Karger-Stein variant achieving an expected running time of O(n^2 \log n) to find a global minimum cut with high probability. Recent deterministic advancements have reduced the complexity to near-linear time, including a 2021 algorithm by Jason Li that runs in m^{1+o(1)} time for weighted graphs using recursive contraction and isolation techniques,[24] and a 2024 algorithm by Jason Li for weighted graphs in O(m \log^3 n) time using sparse clustering techniques.[25]Max-Flow Min-Cut Theorem
Statement
The max-flow min-cut theorem states that, in a flow network with designated source vertex s and sink vertex t, the value of any maximum s-t flow equals the capacity of any minimum s-t cut.[19] Formally, for a flow network G = (V, E) with capacity function c: E \to \mathbb{R}_{\geq 0}, \max \{ |f| \} = \min \{ c(S, T) \mid S \subseteq V, \, s \in S, \, t \in T, \, S \cap T = \emptyset \}, where |f| denotes the value of flow f (the net flow leaving s or entering t), and c(S, T) is the capacity of the s-t cut (S, T), defined as the sum of capacities of edges directed from S to T.[3] The theorem holds under the standard assumptions of flow networks: edge capacities are finite and non-negative; any feasible flow f satisfies the capacity constraints $0 \leq f(e) \leq c(e) for all edges e \in E and the conservation of flow, meaning that for every vertex v \in V \setminus \{s, t\}, the total inflow equals the total outflow.[26] This central result was proved by Lester R. Ford Jr. and Delbert R. Fulkerson in their seminal 1956 paper on network flows.[3] A key corollary, also established by Ford and Fulkerson, is that if all edge capacities are integers, then there exists a maximum flow that takes integer values on every edge.[27]Implications
The proof of the max-flow min-cut theorem provides intuition through the Ford-Fulkerson method's use of augmenting paths and residual graphs. A flow f is maximum if and only if there is no augmenting path from source s to sink t in the residual graph G_f. In this case, define S as the set of vertices reachable from s in G_f (including s), and T = V \setminus S (including t). The net flow across the cut (S, T) equals the value of f, since edges from S to T are saturated (residual capacity zero forward) and edges from T to S carry no residual backward flow that would allow augmentation. This establishes that the capacity of (S, T) bounds the flow value from above and equals it for the maximum flow, proving the cut is minimum.[27][28] This theorem has key implications for computation and optimization. It allows the minimum s-t cut to be found indirectly by first computing a maximum flow using any valid algorithm, such as Edmonds-Karp or Dinic's, after which the reachable set in the residual graph identifies the cut partitions. Furthermore, the theorem embodies strong duality in linear programming: the primal LP maximizes flow subject to capacity constraints, while the dual minimizes cut capacity subject to edge coverage, with optimal values equal.[28][29] Extensions of the theorem apply to broader settings. For multicommodity flows, where multiple source-sink pairs share network capacities, Hu (1963) extended the equality to two commodities in undirected graphs. For general multicommodity flows, approximate versions hold, such as the max-flow being within O(\log n) of the min-cut in n-node undirected graphs. In undirected graphs, the theorem applies directly by modeling each undirected edge \{u,v\} with capacity c as two directed edges (u,v) and (v,u), each with capacity c. The theorem holds for any flow algorithm that correctly computes the maximum flow, independent of the specific method.[30] As an illustrative example, consider a flow network with vertices s, u, t and a single edge from s to u with capacity 3, followed by an edge from u to t with capacity 3. The maximum flow is 3, saturating both edges, and the minimum cut (e.g., \{s\}, \{u,t\}) has capacity 3, matching the flow value; no augmenting path remains in the residual graph.[31]Algorithms
Deterministic Algorithms
The Ford-Fulkerson method is a foundational deterministic algorithm for computing the maximum flow in a flow network, which, by the max-flow min-cut theorem, also yields the minimum s-t cut as the set of nodes reachable from the source in the residual graph after saturation.[3] It operates by iteratively finding augmenting paths from source to sink in the residual graph and augmenting the flow along each such path until no more paths exist, ensuring termination for integer capacities.[3] The Edmonds-Karp algorithm refines the Ford-Fulkerson method by selecting augmenting paths using breadth-first search (BFS), which guarantees polynomial time complexity of O(VE^2) for a graph with V vertices and E edges.[32] This implementation bounds the number of augmentations to O(VE) and each BFS to O(E), making it efficient for sparse graphs.[32] To illustrate, consider a simple flow network with vertices s, a, b, t and edges with capacities: s \to a: 3, s \to b: 2, a \to b: 1, a \to t: 2, b \to t: 3.- Iteration 1: BFS finds path s \to a \to t with bottleneck 2; augment flow by 2. Residual updates: s \to a: 1, a \to t: 0, t \to a: 2.
- Iteration 2: BFS finds path s \to b \to t with bottleneck 2; augment by 2. Residual: s \to b: 0, b \to t: 1, t \to b: 2.
- Iteration 3: BFS finds path s \to a \to b \to t with bottleneck 1; augment by 1. Residual: s \to a: 0, a \to b: 0, b \to t: 0.