Skip to main content

Max-Flow Min-Cut Duality

What This Concept Is​

A cut (S, T) of a flow network is a partition of V with s in S and t in T. The capacity of the cut is the total capacity of edges going from S to T:

c(S, T) = sum over u in S, v in T of c(u, v)

Backward edges from T to S do not contribute.

The max-flow min-cut theorem (Ford-Fulkerson 1956) states: the maximum value of any flow equals the minimum capacity of any cut.

max |f| = min c(S, T)

Moreover, the following are equivalent for a flow f:

  1. f is a maximum flow.
  2. The residual graph G_f contains no augmenting s-t path.
  3. |f| = c(S, T) for some cut (S, T).

At a max flow:

  • every edge from S to T in any minimum cut is saturated (flow equals capacity)
  • every edge from T to S carries zero flow
  • S is exactly the set of vertices reachable from s in the residual graph G_f

The third bullet gives you an effective algorithm for recovering a minimum cut: after running max flow, do a BFS from s in the residual; everything reachable is S, the rest is T.

The theorem is also a special case of linear programming duality - max flow is an LP, min cut is its integral dual, and LP duality plus total unimodularity of the constraint matrix gives integer-capacity integer optimality.

Why It Matters Here​

Min cuts are the "dual language" of max flow. Many problems are cleaner to state as min cuts than as max flows:

  • Image segmentation. Pixels split into "foreground" and "background" - a minimum-cost cut on a pixel grid graph (Boykov-Kolmogorov).
  • Project selection. Pick a subset of projects to maximize profit subject to prerequisites - formulated as a min-cut in a source-sink graph.
  • Baseball elimination. Decide whether a team is still in contention - reducible to feasibility of a specific max flow.
  • Network reliability. The minimum number of edges whose removal disconnects s from t is the min s-t edge cut, and equals the max number of edge-disjoint s-t paths (Menger's theorem).
  • Data-integrity cuts. Minimum number of node failures that partition a cluster - vertex-cut duality via vertex splitting.

Reading a problem as a min cut often reveals the modeling move that a max-flow framing obscures.

Concrete Examples​

Example 1. On the network

cut (S, T)capacity formulavalue
({s}, {a,b,t})c(s,a) + c(s,b)10 + 5 = 15
({s,a}, {b,t})c(s,b) + c(a,b) + c(a,t)5 + 15 + 10 = 30
({s,a,b}, {t})c(a,t) + c(b,t)10 + 10 = 20
({s,b}, {a,t})c(s,a) + c(b,t)10 + 10 = 20

Max flow = 15 equals the min cut ({s}, {a,b,t}). Saturated edges: (s,a), (s,b). A max-flow assignment sends s -> a -> t: 10 and s -> b -> t: 5.

Example 2 (project selection). Three projects with profits 10, 20, 30 and prerequisites (P1 needs A, B; P2 needs B, C; P3 needs C, D); equipment costs A=5, B=7, C=4, D=9.

(Project arcs to equipment have infinite capacity.) Min cut encodes "take these projects, reject those equipment items." Max profit = sum of project revenues minus min cut value.

Common Confusion / Misconceptions​

  • "Count every edge between S and T." No - only forward S -> T edges; backward T -> S edges don't contribute to c(S, T).
  • "The min cut is unique." Not necessarily - multiple cuts can share the minimum capacity. The residual-BFS construction returns the "leftmost" min cut (closest to s); a symmetric BFS from t returns the "rightmost."
  • "Vertex cut = edge cut." They differ. Vertex cuts are reduced to edge cuts by splitting each vertex v into v_in -> v_out with appropriate capacity.
  • "Min cut means minimum number of edges." Only in unit-capacity networks. With weighted capacities, min cut optimizes total capacity.
  • "Max-flow min-cut is a statement about graphs." It is a linear-programming duality result that happens to admit a combinatorial proof via Ford-Fulkerson.

How To Use It​

Once you have computed a max flow, recover a min cut like this:

run max-flow to get flow f and residual G_f
S := { v : v reachable from s in G_f using residual edges with capacity > 0 }  (BFS/DFS)
T := V - S
min cut edges := { (u, v) in E : u in S, v in T }

To model a problem directly as a min cut:

  1. build a source-sink graph whose (S, T) cuts correspond to the decisions you want to make
  2. assign edge capacities so that c(S, T) equals the cost of the decision encoded by that cut
  3. add "infinite-capacity" edges to enforce hard constraints (which cannot be in any min cut)
  4. solve max flow; the resulting min cut is your answer

Modeling checklist:

  • item-set on one side = reachable from s in residual (must include s; must exclude t)
  • constraint "if X is chosen, Y must be chosen" = infinite-capacity arc X -> Y
  • cost c of choosing X = finite arc s -> X or X -> t depending on direction
  • profit p for X = subtract p from the cut by placing an arc s -> X with capacity p (and add p to the constant term)

Transfer / Where This Shows Up Later​

  • S3 (systems). Failure-tolerance analysis: minimum number of node/link failures that partitions a service.
  • S4 (compilers). Register allocation via min-cut reductions; partitioning instructions across issue slots.
  • S5 (OS). Process-migration cost analysis, NUMA partitioning to minimize cross-socket traffic.
  • S6 (databases). Partitioning tables to minimize cross-shard join traffic; replication planning under failure-domain constraints.
  • S7 (DDD). Identifying the cheapest "knife" that separates two sub-systems when splitting a monolith - a min-cut over dependency weights.
  • S8 (distributed). Network partitioning analysis, choosing quorum topologies, routing algorithms that minimize worst-case congestion.

Back-link to concept 17 (Ford-Fulkerson method), forward to concept 20 (bipartite matching via flow).

Check Yourself​

  1. Prove in one sentence why |f| <= c(S, T) for any flow f and any cut (S, T).
  2. Why does the residual BFS from s yield a valid min-cut side?
  3. Give one problem that is easier to state as min cut than as max flow.
  4. Why is |f| = c(S, T) possible only when f is a max flow and (S, T) is a min cut?
  5. Show the vertex-splitting transformation that reduces a vertex cut to an edge cut.
  6. What is Menger's theorem, and why is it a special case of max-flow min-cut?

Mini Drill or Application​

Model the following as min cuts and compute the answer on a small instance:

  1. Given a graph and two terminals s, t, find the minimum number of edges whose deletion separates them.
  2. Given a list of projects with profits and prerequisites, select a subset maximizing total profit.
  3. Given a bipartite grid of pixels with foreground/background per-pixel scores and neighbor-smoothness scores, compute an optimal binary labeling.
  4. Given a graph with source s and a set of sink candidates, find the minimum edge cut separating s from any sink.
  5. Prove Menger's edge form: compute max s-t edge-disjoint paths and min edge cut on several small graphs; confirm equality.

For each, state (V, E, s, t, capacities) explicitly before running any algorithm.

Read This Only If Stuck​