14. Incremental Improvement: Matching

What this lecture covers

This lecture answers why the Ford-Fulkerson algorithm actually produces a maximum flow, how fast it runs, and how network flow can be used as a general-purpose tool to solve problems that don't look like flow problems at first. It is the second of two lectures on network flow in MIT's 6.046, following the lecture that introduced flow networks, cuts, and residual graphs.

By the end, you can state and prove the max-flow min-cut theorem, explain why Ford-Fulkerson's running time depends on how augmenting paths are chosen (including a pathological example with edge capacities around 10^9), state the Edmonds-Karp improvement using breadth-first search, and set up a max-flow instance to decide whether a sports team is mathematically eliminated from first place.

Key ideas

• Residual network and augmenting paths (recap): G_f contains an edge (u,v) whenever the residual capacity c(u,v) - f(u,v) is strictly positive; an augmenting path is any path from s to t in G_f, and its residual capacity is the minimum edge capacity along it.
• Ford-Fulkerson algorithm: start with zero flow; while an augmenting path exists in G_f, augment the flow by the path's residual capacity; when no augmenting path exists, the flow is maximum.
• Max-flow min-cut theorem: three statements are equivalent for a flow f — some cut is saturated (f = c(S,T)), f is a maximum flow, and f admits no augmenting path; the lecture proves 1 implies 2, 2 implies 3, and 3 implies 1.
• Constructing the saturating cut: given a flow with no augmenting path, the set of vertices reachable from s in G_f forms one side of a cut whose forward edges are all saturated, which directly proves 3 implies 1.
• Choice of augmenting path matters: a poorly chosen (depth-first) sequence of augmenting paths can force close to 2 * 10^9 iterations on a four-vertex graph with large capacities, even though two iterations suffice with a better choice.
• Edmonds-Karp algorithm: choosing the augmenting path by breadth-first search (shortest path by edge count) bounds Ford-Fulkerson to O(VE) augmentations, giving an overall running time of O(VE^2).
• Faster max-flow algorithms: the lecture briefly surveys the history of improved bounds (Dinic, King-Rao-Tarjan's O(VE log(E/(V log V) V)), Orlin's O(VE), and newer work), without covering their proofs.
• Baseball elimination via max flow: modeling remaining games between teams as flow-network capacities lets you determine whether a team can still finish in first place, even in cases where simple arithmetic ('wins + remaining games < leader's wins') is not decisive.

Walkthrough

Review and the Ford-Fulkerson algorithm in code (0:00)

The lecture reviews flow networks, cut capacity, and residual networks from the previous session, then writes out the Ford-Fulkerson algorithm explicitly: initialize flow to zero, repeatedly find an augmenting path in the residual network, and augment the flow by its residual capacity until no augmenting path remains. A small worked example (a two-hop network with a bottleneck edge) shows the flow increasing from zero to its maximum in two augmentations.

Statement of the max-flow min-cut theorem (16:10)

The theorem states that three conditions on a flow f are equivalent: f saturates some cut's capacity, f is a maximum flow, and f admits no augmenting path. The lecture explains that proving 3 implies 2 directly is harder than chaining 1 implies 2, 2 implies 3, and 3 implies 1, which together establish the same equivalence and, crucially, justify why Ford-Fulkerson's termination condition (no augmenting path) guarantees optimality.

Proving 1-implies-2 and 2-implies-3 (21:16)

Both directions follow almost immediately from definitions. If a cut is saturated, the flow can't exceed its capacity, so it must be maximum. If an augmenting path exists, its residual capacity is strictly positive, so the flow value could be increased, contradicting maximality — proving that a maximum flow cannot have an augmenting path.

Proving 3-implies-1: constructing the cut (24:18)

This is the heart of the proof. Given a flow with no augmenting path, the lecture defines S as the set of vertices reachable from s in the residual network G_f, and T as everything else; t cannot be in S since there's no augmenting path. For any edge (u,v) in the original graph with u in S and v in T, the absence of a residual edge means the edge must be fully saturated (f(u,v) = c(u,v)), because otherwise v would be reachable and belong to S. Summing over all such edges shows the flow across the cut equals the cut's capacity, completing the proof and explaining why Ford-Fulkerson works.

Running time and a pathological example (36:32)

Because Ford-Fulkerson doesn't specify how to choose augmenting paths, the lecture shows a small four-vertex network with capacities around 10^9 where repeatedly picking paths through the center vertex forces close to two billion iterations, even though the optimal flow requires only two. This motivates the Edmonds-Karp refinement: choosing the augmenting path via breadth-first search (shortest path by number of edges) bounds the algorithm to O(VE) augmentations, each costing O(V+E) for the search, giving O(VE^2) overall. The lecture briefly surveys later improvements (Dinic, King-Rao-Tarjan, Orlin) without proof.

Baseball elimination via max flow (51:45)

Using a modified 1996 American League East standings table, the lecture poses the question of whether a trailing team (Detroit) can still finish in first place given its current wins, losses, and remaining games, including games remaining against each other division rival. A simple check (wins plus remaining games less than the leader's current wins) is shown to be sufficient but not necessary for elimination; a worked example shows a team can be eliminated even when that simple check doesn't trigger. The lecture then builds a flow network where the source connects to nodes representing pairs of teams still to play each other (capacity equal to games remaining between them), those connect to nodes for each individual team (infinite capacity), and each team node connects to the sink with a capacity computed from how many more games it can win without exceeding what the analyzed team could achieve. The team is eliminated exactly when the max flow is strictly less than the total games remaining among the other teams — found here by identifying a min cut of value 25 against a required 26, using the max-flow min-cut theorem rather than running the algorithm step by step.

Before you watch

• Watch the previous 6.046 lecture on flow networks, cuts, and residual networks; this lecture assumes that notation and the definitions of flow value, cut capacity, and augmenting paths.
• Comfort with proof by contradiction and set-based arguments (the implicit summation notation from the prior lecture) is helpful for the max-flow min-cut proof.

Check your understanding

1. Walk through the proof that 3 implies 1 in the max-flow min-cut theorem: why must every edge from the reachable set S to T be saturated?
2. Why can a bad choice of augmenting paths cause Ford-Fulkerson to take a number of iterations proportional to the edge capacities, and how does breadth-first search in Edmonds-Karp avoid this?
3. In the baseball elimination construction, what does an edge's capacity from a 'team pair' node to an individual team node represent, and why does saturating all edges out of the source correspond to 'playing all remaining games'?
4. Why is 'wins + remaining games < leader's wins' a sufficient but not necessary condition for a team's elimination, and what kind of interaction between other teams can eliminate a team even when this check fails?