Recitation 7: Network Flow, Edmonds-Karp, and Matching

What this lecture covers

This MIT 6.046 recitation works through the runtime proof for the Edmonds-Karp algorithm, a refinement of Ford-Fulkerson that always augments along the shortest path (fewest edges) in the residual graph. It answers a question left open by Ford-Fulkerson: how many augmenting iterations are actually needed before the algorithm halts, and why picking the shortest path each time is what makes the bound provable.

The recitation sits after the main lectures on network flow and builds toward two applications: bipartite matching and bipartite vertex cover. After watching, you should be able to reproduce the monotonicity argument for shortest-path distances in the residual graph, explain why an edge can only be "critical" a bounded number of times, and set up a max-flow network that solves a matching or cover problem.

Key ideas

• Ford-Fulkerson recap: build a residual graph from the current flow, find any augmenting path from source to sink, push flow equal to the path's minimum residual capacity, and repeat.
• Edmonds-Karp: identical to Ford-Fulkerson except it always chooses the shortest augmenting path (by number of edges), which is what makes the number of iterations boundable.
• delta_f(v): the shortest-path distance from the source to vertex v in the residual graph for flow f.
• Monotonicity lemma: delta_f(v) never decreases as the flow is augmented over time, for any vertex v.
• Critical edge: an edge on the shortest augmenting path with the smallest residual capacity; it disappears from the residual graph once used.
• Bound on iterations: each edge can be critical at most V/2 times, so the total number of augmentations is O(VE), and since each iteration costs O(E), the overall runtime is O(VE^2).
• Bipartite matching as max flow: connect a source to every person and every task to a sink, all with capacity 1, and connect a person to a task if they can perform it; the max flow equals the maximum matching.
• König-style equivalence: the minimum vertex cover of a bipartite graph has the same size as the maximum matching, and a cover can be constructed from a maximum matching using alternating paths.

Walkthrough

Ford-Fulkerson and Edmonds-Karp recap (0:00)

The instructor recaps Ford-Fulkerson: build the residual graph, find any source-to-sink path, augment by the path's bottleneck capacity, and repeat with the updated residual graph. Edmonds-Karp changes only the path-selection step, requiring a breadth-first search for the shortest path. The classic pathological example (large parallel capacities linked by a small middle edge) shows why arbitrary path choice can take far more iterations than picking the shortest path each time.

The monotonicity lemma (9:35)

To bound the number of iterations, the recitation first proves that delta_f(v), the shortest-path distance from source to v in the residual graph, never decreases across iterations. The proof is by contradiction: assume some vertex's distance drops after an augmentation, pick the vertex v with the smallest such distance, and look at its predecessor u on the new shortest path. Case analysis on whether edge (u,v) existed in the old residual graph (it either was already there, or it was created by reversing an edge used in the augmenting path) shows in both cases that the assumed decrease is impossible.

Bounding how often an edge can be critical (27:16)

Using the monotonicity lemma, the recitation shows that if edge (u,v) is critical (its residual capacity is the path's bottleneck) in one iteration, it can only become critical again after the flow later needs to be augmented back along (v,u). Comparing delta values before and after shows that delta(u) must increase by at least 2 between successive times (u,v) is critical. Since delta is bounded by V, each edge is critical at most V/2 times, giving O(VE) total augmentations and an O(VE^2) runtime for Edmonds-Karp.

A faster alternative: Dinic's algorithm (32:30)

The instructor briefly describes Dinic's algorithm, which augments along all shortest paths in a single phase rather than one path at a time, reducing the number of phases to O(V) and giving an overall O(V^2 E) runtime. He also relays the story behind the algorithm's name: it is credited to a different person than the one usually associated with popularizing it, which is why the name in common use is a misattribution.

Bipartite matching as a max-flow problem (35:31)

The first application: given people and tasks connected by edges representing "can perform," find the largest possible assignment where each person does at most one task and each task gets at most one person. The recitation shows this is a bipartite graph problem and demonstrates a suboptimal matching before setting up the max-flow reduction: add a source connected to every person and a sink connected to every task, all edges capacity 1. A max flow of value K corresponds directly to a matching of size K, since each person and task can carry only one unit of flow.

Bipartite cover and its equivalence to matching (42:00)

The second application is minimum vertex cover on a bipartite graph: choose the fewest vertices so every edge touches at least one chosen vertex. The recitation argues that the minimum cover size equals the maximum matching size. It shows a cover of size K is a lower bound from any matching of size K (each matched edge needs its own cover vertex), then constructs an actual cover of size K from a maximum matching using alternating paths, confirming the equality.

Before you watch

• Know the Ford-Fulkerson method and residual graphs from the network flow lectures.
• Be comfortable with proof by contradiction and shortest-path (BFS) reasoning.
• Review the definition of bipartite graphs before the matching section.

Check your understanding

1. Why does always picking the shortest augmenting path guarantee a polynomial bound on the number of iterations, when arbitrary path choice does not?
2. In the monotonicity proof, why does the argument split into two cases based on whether edge (u,v) existed in the old residual graph?
3. Explain why an edge can be critical at most V/2 times.
4. How does capping every edge in the matching network at capacity 1 enforce that each person and task is used at most once?
5. Why does a maximum matching of size K imply a minimum vertex cover of size exactly K, rather than just at least K?