Max-Flow Min-Cut Duality
What This Concept Is
An s-t cut partitions vertices into S and its complement with s in S and t outside. Its capacity sums original directed capacities from S to outside, not both directions. Any feasible flow has value at most any cut capacity: net flow across the cut equals source value by conservation, and outgoing flow cannot exceed outgoing capacities.
Why It Matters Here
An equal-value feasible flow and cut form independently checkable lower and upper bounds. Their equality certifies optimality without rerunning the solver's augmentation strategy. A scalar "maximum" value alone is not such a certificate.
Concrete Examples
After no augmenting path remains, let S be vertices reachable from s in the positive residual graph. Then t is outside S. Every original S→outside edge is saturated, otherwise residual reachability would cross it. Every original outside→S edge carries zero flow, otherwise its backward residual edge would cross outward. Consequently net flow across the cut equals its capacity, proving maximum flow and minimum cut together.
In the unit reassignment network, source has two outgoing capacity-1 edges, so
cut {s} has capacity 2. The feasible reassigned flow of value 2 meets that
bound. A flow of value 1 plus the same cut only bounds the optimum between 1
and 2; it does not certify optimality.
Common Confusion / Misconceptions
The source side is residual reachability, not original graph reachability. A minimum cut need not be unique, and a minimum cut capacity is not the same as the minimum number of edges unless capacities model that objective. Cut-based project selection or image labeling requires a separate reduction and sign/ submodularity assumptions; a plausible diagram alone does not establish it.
How To Use It
Verify each original edge's flow range, all nonterminal balances, both terminal net values, cut membership and cut capacity. For tiny graphs, enumerate all source-containing/sink-excluding subsets as an independent optimum oracle. Certificate checking is polynomial; cut enumeration is exponential and for small tests only.
Check Yourself
- Why are incoming cut edges subtracted in net flow?
- Why must outgoing cut edges be saturated at termination?
- What forces incoming cut-edge flow to zero?
- What can unequal feasible-flow and cut values establish?
Mini Drill or Application
Given a returned flow vector and cut, implement a verifier independently of residual augmentation. Corrupt one internal-edge flow while leaving the reported value unchanged and ensure conservation rejects it. Corrupt the cut separately. See P19.
Read This Only If Stuck
Find max-flow min-cut proof and optimality certificates in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.