Bipartite Matching via Flow

A problem with no pipes in it

Here is a problem that looks nothing like a network. On the left sit applicants; on the right sit jobs; draw an edge whenever an applicant is qualified for a job. You want to hire as many people as possible, with each applicant taking at most one job and each job filled by at most one person. A set of edges that share no endpoint is a matching, and we want a maximum matching — as many simultaneous hires as the qualifications allow. There is no source, no sink, no capacity anywhere. So why is this the headline application of max-flow?

Because the answer is a tiny act of modeling — reshaping a problem until its max flow is exactly the number you wanted. The graph being bipartite (two sides, every edge crossing between them) is the special ingredient that makes the reshaping faithful. A maximum matching is a 'choose the largest valid set' question, and that is precisely the flavor of question flow is built to answer. The work is not inventing a clever algorithm; it is drawing four extra edges and pointing every arrow the right way.

The construction: bolt on a source and a sink

Take the bipartite graph with left set L and right set R. Add a brand-new source s and a brand-new sink t. From s draw an edge to every left vertex; from every right vertex draw an edge to t; and orient each original qualification edge from its left endpoint to its right endpoint. Now give every edge in the whole network a capacity of exactly 1. That single number is the entire trick: a capacity of 1 on s->u says applicant u can be used at most once; a capacity of 1 on w->t says job w can be filled at most once; and capacity 1 on u->w says that pairing is either taken whole or not at all.

          s
        / | \         (each s->left edge has capacity 1)
      u1  u2  u3
      |    \X/
      w1   w2  w3      (each left->right edge = a qualification, cap 1)
        \   |   /
          t            (each right->t edge has capacity 1)

Now the claim that earns its keep: integer flows in this network correspond exactly to matchings, and the value of the flow equals the size of the matching. Why integer? Because all capacities are whole numbers, the integrality property of max-flow guarantees a maximum flow that is whole-number on every edge — so each edge carries either 0 or 1, never a fraction. An edge u->w carrying 1 means 'hire u for w'; the capacity-1 caps at s and t forbid any applicant or job from being used twice. So a value-k flow is k disjoint hires, and a maximum-value flow is a maximum matching. We did not solve matching; we restated it.

Augmenting paths become alternating paths

Run any max-flow algorithm on this gadget and something beautiful happens to the augmenting paths. Recall an augmenting path walks from s to t in the residual graph, freely using forward edges (room left) and backward edges (undo). In the matching network, strip off the s and t bookends and what remains in the middle is an alternating path: it alternates between qualification edges currently NOT in the matching (forward) and edges currently IN the matching (backward). Pushing one unit along it flips every edge it touches — unmatched pairs become matched, the one matched pair in the way becomes unmatched — and the matching grows by exactly one.

1. Suppose u1 is matched to w1, and now applicant u2 is qualified only for w1. Naive greed is stuck: w1 is taken, so u2 seems unhireable.
2. But suppose u1 is also qualified for an unfilled job w2. The residual graph offers an alternating path: u2 -> w1 (forward, unmatched), w1 -> u1 (backward, the matched edge), u1 -> w2 (forward, unmatched).
3. Augment by 1: now u2 takes w1 and u1 moves to w2. We did not displace anyone — we rearranged. The matching went from one hire to two, exactly the undo-an-old-choice power the residual graph was built for.

This is why naive greedy matching — pair up whatever you see, never reconsider — can fall short, the same crack we met in the greedy rung: locally fine, globally suboptimal. The fix here is identical to the fix for flow, because they are the same fix. Berge's theorem makes it a clean stopping rule: a matching is maximum exactly when no augmenting (alternating) path exists, which is precisely when no s-to-t residual path exists. The two stories are one story wearing two costumes.

Reading König's theorem off the minimum cut

Now collect the dividend. When the flow is maximum, the max-flow min-cut theorem hands us a minimum cut of equal capacity. Trace what a finite-capacity cut means in the matching gadget: it can only cut s->u edges and w->t edges (the middle edges, by König's classic argument, can be avoided), and a chosen set of those corresponds to a set of vertices — left vertices whose s-edge is cut, plus right vertices whose t-edge is cut — that together touch every qualification edge. A set of vertices touching every edge is a vertex cover. So the minimum cut's capacity equals the minimum vertex cover's size.

Chain the equalities and a famous theorem appears for free. Maximum matching equals max flow (our construction), max flow equals min cut (the duality theorem), and min cut equals minimum vertex cover (the cut reading). Therefore in any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover — this is König's theorem, a celebrated min-max duality, and flow hands it to us with almost no extra work. The largest set of disjoint edges and the smallest set of vertices covering all edges are the same number.

What it costs, and the honest fine print

How fast is this? Every augmenting path raises the matching by 1, so there are at most V augmentations, and each is one graph search costing O(E). That gives a simple O(V*E) bound — already polynomial, already a fine answer. But because all capacities are 1, this is a unit-capacity network, exactly the setting where Dinic's algorithm shines: it runs in O(E * sqrt(V)) here, finding many shortest augmenting paths per phase instead of one. The matching-native version of that idea is the Hopcroft-Karp algorithm, which augments along a whole maximal set of shortest alternating paths each round and likewise hits O(E * sqrt(V)).

Two cautions keep you honest. First, those are worst-case asymptotics; the usual hidden-constant caveats apply, and on real graphs the plain O(V*E) method often finishes long before its bound — asymptotics describe scaling, not a verdict at every size. Second, and more important: this entire trick relies on the graph being bipartite. Plain max-flow on a general (non-bipartite) graph does NOT correctly model matching, because an odd cycle can manufacture a flow with no matching behind it. General matching is solvable in polynomial time too, but it needs Edmonds' blossom algorithm, a genuinely different and harder idea — not flow.

Finally, what if the edges carry weights — pay applicant u $30 to do job w, and you want the cheapest full set of hires? Capacity-1 max-flow ignores weights entirely; it only counts. For that you climb to min-cost max-flow or the Hungarian algorithm, which the next guide on modeling problems as flow sets up. The lesson of this guide is the cleanest case: when a problem is 'pick the largest valid pairing on two sides', draw a source, a sink, and unit capacities, and let a max-flow algorithm you already trust do the work — then read the duality theorems off the cut for free.