Lecture 15: Max-Flow Min-Cut Theorem

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 (xij <= uij). The dual LP minimizes the sum of alphaij uij, subject to constraints derived from the primal variables, where alphaij relates to the capacity constraints and betai relates to the conservation constraints. By setting betas = 0 and betat = 1 and choosing alphaij = max(0, betaj - betai), 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 uij - xij and backward edges have capacity xij) 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.