Programming

Maximum Flow

Pump fluid through a pipe network until the seams burst. The instant the flow chokes, the network reveals an invisible geometric fault-line: a razor-thin cut across the world where every single pipe is gorged to capacity.

Greedy routing chokes on saturated pipes; push residual flow to close the duality gap from 8 to 0.

Mission 10about 10 min

Push fluid through residual network paths until the capacity gap closes to zero against the minimum cut.

  1. Augment flow along forward pipes while adding reverse cancellation capacity
  2. Watch the primal-dual gap shrink from 8 down to 0 on the dashboard
  3. Identify the saturated bottle-neck edges that form the minimum cut certificate

After thisYou can solve max-flow, min-cut, bipartite matching, and network interdiction problems with exact dual certificates.

Short on timeThe LPDualityDashboard panel in §4

The Five-Junction Pressure Chamber

3 minthe hook

On the dashboard below, the gap between the best flow and the cheapest cut starts at 8. It closes to 0 only when a cut appears whose forward pipes are all saturated, and that cut is the certificate.

Five steel junctions sit under pressure, labelled , , , , and , linked by seven one-way conduits. Their ceilings: holds 2, holds 6, holds 2, holds 3, holds 2, holds 7, and holds 3. Fluid is injected at and escapes only at , never accumulating at an intermediate junction.

The picture is the fault line: the flow is pressure pushing through the rock, and the crack is the saturated set of pipes that separates the source side from the sink side. Nothing crosses the fault line faster than the pipes in it can carry.

Before tracing a single route: what is the maximum rate of fluid that can reach the sink?

NextWhy does greedy pipe allocation choke when the first path saturates the wrong branch?

The Phantom Reverse Flow

2 minthe trap

The naive operational impulse is greedy: pump fluid along any route with spare room, and halt when no path from to looks open. But that stopping condition merely reports where your initial guesses ran out of room, not where the network chokes.

A pipe already carrying volume holds a hidden power: reverse capacity. By pushing backwards along an active pipe, you cancel a prior commitment and reroute flow elsewhere at zero net cost. To discover optimal throughput, search must proceed through the residual graph, where every unit of forward flow spawns an equivalent backward path.

Greedy searches search forwards, but mathematical optimality requires an inescapable upper bound. To prove that 7 is the true ceiling, you cannot merely shrug after running out of paths; you must present a concrete geometric barrier that forbids 8. That certificate is a cut.

NextHow do residual backward edges give the algorithm the ability to undo prior flow?

The Duality of Fluid and Steel

2 minthe invariant

The physical state is a feasible flow: an assignment to each pipe satisfying capacity constraints and strict conservation at every junction except and . The aggregate throughput is the total volume spilling out of the source:

Here denotes the set of conduits directed from inside a subset of junctions to the outside world.

Its mathematical mirror is a cut: a partition of the vertices into and its complement, with and . The cut’s capacity is the gross capacity of all pipes crossing the boundary:

Any cut whatsoever provides an absolute ceiling on every feasible flow. The magic happens when the fluid rate equals the cut capacity: at that instant, both are unconditionally certified optimal.

NextHow does the max-flow min-cut theorem prove that capacity equals bottleneck throughput?

The Vanishing Gap and Total Unimodularity

2 minthe algebra

The primal question is a linear program: maximise throughput subject to non-negative edge bounds and Kirchhoff’s current conservation law at every junction.

Summing the conservation equations over any subset containing the source causes all internal pipe cancellations. What remains is the fundamental inequality of weak duality:

The gap is nonnegative for every flow and every cut. In the dashboard below, this gap begins at 8 and drops strictly downward, certifying progress toward the bottleneck.

The linear-programming dual assigns a potential to each junction and a shadow price to each pipe, normalised so . The dual program minimises total capacity cost subject to price differences . Integrating over potential thresholds reveals that this dual optimum is precisely the minimum cut.

Theorem (Ford & Fulkerson 1956; Elias, Feinstein & Shannon 1956). The maximum flow value equals the minimum cut capacity. The residual graph provides both the algorithm and the certificate: when no augmenting path remains from to , the set of vertices still reachable from defines a cut where every forward pipe is saturated and every backward pipe is dry.

Why does an integer plumbing problem never yield fractional trickles? The junction-pipe incidence matrix has exactly one and one in each column, making it totally unimodular (Hoffman & Kruskal 1956). Every basic feasible solution of a totally unimodular system with integer bounds is an integer vector, guaranteeing that integer capacities yield pure integer flows.

Augmentations on a four-junction diamond, hand-computed

1e01e11e21e31e41e51e61e70246log₁₀ of the capacity C on each decisive pipeaugmentations
Edmonds–Karp (shortest path)Ford–Fulkerson (worst path choice)

On a simple four-node diamond with high capacity , an unfortunate choice of augmenting paths can bounce a single unit back and forth, consuming steps. Edmonds & Karp (1972) tamed this by always augmenting along shortest paths via breadth-first search, guaranteeing termination in steps regardless of capacity magnitudes.

Ford–Fulkerson halts once no augmenting path remains. What happens if pipe capacities are irrational real numbers and paths are chosen arbitrarily?

NextHow does Ford-Fulkerson augmentation eliminate the duality gap between flow and cut?

Driving the Residual Augmentation

2 minthe simulation

The seven pipes await your command. Step through the execution to watch Edmonds–Karp locate shortest residual routes, update primal flow, and track the shrinking duality gap.

1 minboss round

Step the run to completion. Which exact set of conduits forms the saturated minimum cut?

1 / 4
initial
2623273sabct

initial state: no flow, the residual graph is the capacitated network itself

primal · flow value0
dual · best cut capacity8
gap (dual − primal)8
edgecapacityflowresidual (fwd / bwd)
s → a202 / 0
s → b606 / 0
a → b202 / 0
a → c303 / 0
b → c202 / 0
c → t707 / 0
b → t303 / 0

weak duality: primal ≤ dual at every iteration (gap on the same axis)

02468-0.1-0.0500.050.1augmentation numberobjective value
primal (flow value)dual (best cut capacity)duality gap

Edmonds–Karp augmenting paths (Ford–Fulkerson 1956 / Edmonds–Karp 1972). Weak duality says every flow value is at most every cut capacity, so the primal curve can only meet the dual from below; the gap closes to zero exactly when no augmenting path remains.

Edmonds–Karp on the seven pipes. Step through the augmentations: each green route is a shortest residual s-to-t path, the primal card is the flow value, the dual card is the best cut found so far, and the gap card falls to 0 on the last step. Toggle Show flow to watch saturation and the cut.

Watch the dual card and the gap card, not the flow numbers; the gap reaches 0 on the exact step where every forward pipe of the fault line is saturated.

Press step to augment along shortest residual paths. The green highlighter traces the active augmenting route, while residual capacities adjust in real time. Toggle Show flow to view physical load ratios : saturated pipes turn solid gold, and the terminal cut edges glow with dashed outlines.

After three augmentations, flow reaches 7 and no residual path survives. The duality gap drops from 8 to 0, certifying optimality not through exhaustive search, but through an indisputable physical witness.

NextHow do railway interdiction graphs translate into computer vision segmentation cuts?

From Rail Interdiction to Modern Vision

2 minsystems

Max-flow min-cut was born in a classified 1955 RAND study by T. E. Harris and F. S. Ross analyzing the vulnerability of Soviet railway networks. The US Air Force wanted to identify the minimum number of rail links to sever to paralyze transport from the Soviet heartland into Eastern Europe.

Its reach extends across computer science. Add a supersource and supersink with unit-capacity edges, and max flow solves maximum bipartite matching, where the min-cut yields König’s minimum vertex cover (König 1931; Hall 1935). With unit pipes, Menger’s theorem (1927) on edge-disjoint paths falls out directly.

In modern computer vision, graph cuts segment images into foreground and background in real time (Boykov & Kolmogorov 2004). Pixels become nodes, pairwise gradient affinities become capacities, and the minimum cut carves out pixel-perfect object silhouettes.

Next missionStable MatchingGreedy pairings collapse to rogue defectors; deferred acceptance settles in 4 rounds with 0 blocking pairs.

Circulations, Level Graphs, and Fractional Traps

Hoffman’s circulation theorem (1960) generalises max flow to closed networks with lower and upper capacity bounds . A feasible circulation exists if and only if no cut demands more inbound capacity than outbound limits permit.

Complementary slackness delivers a sharp visual signature: at optimality, every forward cut pipe is fully saturated () and every backward cut pipe is bone-dry (). That is why the cut edges highlighted on the dashboard are precisely the saturated links.

Modern algorithms accelerate this search dramatically. Dinic (1970) pushes blocking flows through layered networks in time, while push–relabel methods (Goldberg & Tarjan 1988) run in .

Attributions

  • Harris & Ross 1955 — Fundamentals of a Method for Evaluating Rail Net Capacities: the classified RAND report formulating maximum network flow.
  • Ford & Fulkerson 1956 — Maximal flow through a network: the augmenting-path method and the max-flow min-cut theorem.
  • Elias, Feinstein & Shannon 1956 — A note on the maximum flow through a network: independent discovery of the theorem.
  • Edmonds & Karp 1972 — Shortest augmenting paths via breadth-first search, establishing strongly polynomial network flow.
  • Hoffman & Kruskal 1956 — Total unimodularity and integral polyhedra.
  • Ford & Fulkerson 1962 and Zwick 1995 — Pathological non-termination on irrational capacities.
  • Boykov & Kolmogorov 2004 — Graph cut optimization for energy minimization in computer vision.