# Lecture 15: Max-Flow Min-Cut Theorem Source: https://www.youtube.com/watch?v=pX-HnYwO454 Recap page: https://rapidrecap.app/video/pX-HnYwO454 Generated: 2025-12-17T16:37:20.724+00:00 --- ## Quick Overview The lecture establishes the Max-Flow Min-Cut Theorem by formulating the maximum flow problem as a Linear Program (LP) and deriving its dual, which corresponds to the minimum cut, ultimately proving that the value of the max flow equals the value of the minimum cut. **Key Points:** - The maximum flow problem seeks the maximum amount of 'whatever' (flow) that can pass from a source (s) to a sink (t) in a network where edges have defined capacities, such as the example flow reaching 9 units. - A cut is defined as a subset of vertices containing 's' but not 't', and the capacity of the cut is the sum of capacities of edges going from the set C to C-bar, establishing that max flow is less than or equal to the minimum cut. - The primal Linear Program maximizes 'z' (the total flow into t) subject to flow conservation constraints (sum of inflow equals sum of outflow for intermediate nodes) and capacity constraints (x_ij <= u_ij). - The dual LP minimizes the sum of alpha_ij * u_ij, subject to constraints derived from the primal variables, where alpha_ij relates to the capacity constraints and beta_i relates to the conservation constraints. - By setting beta_s = 0 and beta_t = 1 and choosing alpha_ij = max(0, beta_j - beta_i), the dual objective function's value is shown to be greater than or equal to the minimum cut. - The augmenting paths algorithm finds the maximum flow by repeatedly finding a path in the residual network (where forward edges have capacity u_ij - x_ij and backward edges have capacity x_ij) and pushing flow until no augmenting path exists, guaranteeing an integer flow if capacities are integers. - König's theorem in bipartite graphs (max matching equals min vertex cover) is proven by transforming the problem into a max-flow problem with unit capacities, where the resulting max flow value equals the matching cardinality, and the min cut corresponds to the vertex cover. **Context:** Professor Peter Shor introduces the concept of maximum flow in a network, where edges possess capacities defining the maximum units of flow that can traverse them from a designated source node 's' to a sink node 't'. The lecture transitions from illustrating an example flow of 9 units to formally proving the Max-Flow Min-Cut Theorem, which is analogous to LP duality, by setting up the primal linear program for max flow and deriving its dual formulation. ## Detailed Analysis The lecture details the Max-Flow Min-Cut Theorem, beginning with an illustrative network example where a flow of 9 units is achieved, and then explaining how to prove this is maximal by identifying a cut with capacity 9 (involving edges with capacities 4, 2, and 3). A cut C is formally defined, and it is shown that the maximum flow cannot exceed the capacity of any cut. The core of the proof involves formulating the max flow problem as a Linear Program (LP) where variables represent flow on each edge, constrained by flow conservation at nodes and edge capacities. Subsequently, the dual of this LP is derived. The dual variables are linked to node potentials (beta_i) and edge constraints (alpha_ij). By strategically setting beta_s=0 and beta_t=1, and assigning alpha_ij = max(0, beta_j - beta_i), the dual objective function is shown to equal the sum over cuts weighted by differences in beta values, leading to the conclusion that the dual solution value is greater than or equal to the minimum cut. Since the primal solution value equals the max flow, strong duality implies max flow equals min cut. Furthermore, Shor introduces the augmenting paths algorithm for finding integer maximum flows when capacities are integers, explaining the concept of the residual network and how the absence of an augmenting path proves the existence of a minimum cut equal to the current flow. Finally, the application to König's theorem in bipartite graphs is briefly covered by mapping matching to flow and vertex cover to the min cut. ### Max Flow Introduction - Network components include source (s), sink (t), and edges with capacities (e.g., 'This 6 says that only six units of flow can pass over this edge') - Example flow achieved is 9 units - A cut defines an upper bound on flow. ### Linear Programming Formulation - Variables x_ij represent flow over edge ij - Primal constraints enforce flow conservation (inflow equals outflow for non-s/t nodes) and capacity limits (x_ij <= u_ij) - Objective is to maximize z, the flow into t. ### Dual LP and Cut Interpretation - Dual variables alpha_ij and beta_i arise from primal constraints - Optimal alpha_ij equals max(0, beta_j - beta_i) - Setting beta_s=0 and beta_t=1 reveals that the dual objective value relates to the sum of capacities along edges where beta_j > beta_i, which form a cut. ### Max-Flow Min-Cut Theorem Proof - Strong LP duality proves max flow equals min cut - The dual solution, constructed using node labels (betas), can be shown to equal the minimum cut value. ### Augmenting Paths Algorithm - This algorithm finds integer flows if capacities are integer - It relies on the residual network, which includes forward edges with remaining capacity (u_ij - x_ij) and backward edges with capacity equal to current flow (x_ij) - Termination when no path exists in the residual network proves optimality via the Min-Cut. ### König's Theorem Application - In bipartite graphs, max matching equals min vertex cover - This is proven by constructing a flow network where middle edges have capacity 1 (or infinity) and source/sink edges have capacity 1 - The max flow corresponds to the matching, and the min cut corresponds to the vertex cover.