7. Sharper iteration bounds and bipartite matching

The O(m)-per-blocking-flow bound is already good; this section attacks the other factor — how many blocking flows are needed 1:15:54.

The path-decomposition argument (unit capacity)

After d iterations, d(s, t) in the level graph is at least d, since it strictly increases each round 1:14:58.
Decompose any remaining max flow in the residual graph into paths; every path has length ≥ d 1:14:58, 1:15:54.
With only m edges, there are at most m/d such paths, so the residual max flow is at most m/d 1:15:54.
Each remaining blocking flow kills at least one unit ⇒ total iterations ≤ d + m/d, for every d 1:16:55.
Minimized at d ≈ √m, giving O(√m) iterations 1:16:55.

Result: O(m) per blocking flow × O(√m) iterations = O(m^{3/2}) max flow, or more precisely O(m · min(√m, n)) 1:17:22.

Consider the layered graph: s, one layer, another layer, t, all edges going forward, all capacities 1 — this is the standard reduction of maximum bipartite matching to s–t max flow (from CS124) 1:18:35, 1:19:36, 1:19:52.
On such graphs the same argument gives d + n/d iterations, minimized at d ≈ √n 1:19:52.
⇒ O(m√n) max flow, hence maximum bipartite matching in O(m√n) 1:20:26.
Comparison: Ford–Fulkerson on the same instance has f* ≈ n, giving only O(mn) 1:20:26.

Approach	Bipartite matching time
Ford–Fulkerson (`f* ≈ n`)	`O(mn)` `1:20:26`
Blocking flows	`O(m√n)` `1:20:26`