Bipartite Matching

A matching in a graph is a set of edges no two of which share an endpoint — every vertex is “covered” by at most one matched edge. A bipartite graph is a graph whose vertex set splits into two disjoint parts L and R such that every edge has one endpoint in each. The Maximum Bipartite Matching (MBM) problem asks: given a bipartite graph, find the largest matching. This problem is fundamental in algorithms because it appears in disguise in countless real-world settings — assigning workers to jobs, matching students to schools, pairing job-applicants to companies, scheduling tasks to time-slots, dating apps. There are two essentially different approaches: (a) reduce MBM to Maximum Flow by giving every relevant edge unit capacity, then run any max-flow algorithm and read off the matching from the flow; (b) specialize the max-flow algorithm directly to the bipartite-unit-capacity structure to get the Hopcroft-Karp algorithm running in O(E · √V). The duality theorem from Min-Cut Max-Flow Theorem gives a striking corollary called König’s theorem: in bipartite graphs, the size of a maximum matching equals the size of a minimum vertex cover — making this otherwise NP-hard problem polynomial only in the bipartite case. For weighted variants (each edge has a cost; minimize total cost over all perfect matchings), the canonical solver is the Hungarian Algorithm.

This is not the same problem as Stable Matching

The two notes share the word “matching” and share the picture — two columns of dots, edges between them — and they are different problems with different objectives, different algorithms, and different correctness criteria. Maximum bipartite matching (this note) optimises a global count and has no notion of preference: the input is a plain edge set, and any two maximum matchings are equally good because “good” means “large”. Stable Matching honours per-agent rankings and optimises nothing global: the input is a complete preference list for every agent, the output is required only to have no blocking pair (a pair who both prefer each other to their assigned partners), and the size of the matching is fixed at n by construction, so counting edges tells you nothing.

	Maximum bipartite matching (this note)	Stable Matching
Input	edge set E ⊆ L × R	a total preference order per agent
Objective	maximise |M|	no objective — satisfy a constraint
Failure condition	an augmenting path exists	a blocking pair exists
Canonical algorithm	Hopcroft-Karp, O(E√V)	The Gale-Shapley Algorithm, O(n²)
Certificate of optimality	Hall violator / König cover	exhaustive blocking-pair check

The practical failure mode is a real one: an engineer sees ranked input, recognises “bipartite matching”, reaches for a Hopcroft–Karp library, and ships a perfect matching that is riddled with blocking pairs because the rankings were never read. Conversely, running deferred acceptance on an instance with no preferences is undefined. Cross-linked deliberately, never merged — see Games and Strategic Systems in C MOC, where the two sit in different rungs of the ladder.

1. Definitions

A graph G = (V, E) is bipartite if V partitions into two disjoint sets L and R (informally, “left” and “right”) such that every edge in E connects an L-vertex to an R-vertex. Equivalently, a graph is bipartite iff it is 2-colorable, iff it contains no odd cycle. (See Bipartite Check for the test algorithm.)

A matching M ⊆ E is a set of edges no two of which share a vertex. A vertex incident to a matching edge is matched; otherwise it is free (or unmatched, exposed).

A matching M is maximum if no other matching has strictly more edges. (Note: maximum ≠ “maximal” — maximal means cannot be extended by adding one edge, which is a weaker, greedy property.) A matching is perfect if every vertex is matched, which requires |L| = |R| and existence of a perfect-matching configuration.

2. Tiny Worked Example

Consider 4 students {u₁, u₂, u₃, u₄} (left) and 4 projects {p₁, p₂, p₃, p₄} (right). Each student has applied for some subset of projects:

u₁ → {p₁, p₂}
u₂ → {p₁}
u₃ → {p₂, p₃}
u₄ → {p₂, p₃, p₄}

The edge set is E = {(u₁,p₁), (u₁,p₂), (u₂,p₁), (u₃,p₂), (u₃,p₃), (u₄,p₂), (u₄,p₃), (u₄,p₄)}.

What’s the maximum matching?

Greedy attempt: assign u₁→p₁, u₂ is now unhappy because p₁ is taken — but u₂ only wants p₁. Assign u₃→p₂, u₄→p₃ (since p₂ is taken). Matching size: 3.

But we can do better. Try u₁→p₂, u₂→p₁, u₃→p₃, u₄→p₄. Matching size: 4 — a perfect matching.

The greedy approach failed because it locked u₁ onto p₁, which u₂ desperately needed. The correct algorithms (augmenting paths, max-flow reduction) handle this via the augmenting path concept, which we now define.

3. Augmenting Paths

Given a partial matching M, an alternating path is a path whose edges alternate between M (matched) and E \ M (unmatched).

An augmenting path is an alternating path that starts and ends at free vertices.

Key insight (Berge, 1957). A matching M is maximum iff there is no augmenting path with respect to M. Why? Given any augmenting path P, we can produce a matching of size |M| + 1 by flipping the edges along P: edges previously in M come out, edges previously out come in. Since P starts and ends at free vertices, the endpoints become matched and the matching size grows by 1.

This is Berge’s Theorem 1, from a three-page note in the Proceedings of the National Academy of Sciences (Berge 1957), and it is worth reading the original statement because Berge’s vocabulary is not ours. He calls a matching edge strong and a non-matching edge weak, an augmenting path an “alternating chain”, and a free vertex a neutral point; his theorem reads “A matching V is maximum if and only if there does not exist an alternating chain connecting a neutral point to another neutral point.” Berge states it for general graphs, not just bipartite ones, which is exactly why it is the foundation for Edmonds’ Blossom Algorithm as well as for everything in this note. His paper also frames Problems 1–3 (maximum independent set, minimum cover, maximum matching) together and observes that in the bipartite case Kuhn’s linear-programming duality applies, while “the linear programming duality used by H. Kuhn no longer subsists when the graph is not bipartite” — the earliest crisp statement of why bipartiteness is the load-bearing hypothesis in §7.

The quantitative version. Berge’s theorem says only that some augmenting path exists when M is suboptimal. Hopcroft and Karp sharpened it into the two facts that make a fast algorithm possible (Hopcroft & Karp 1973, Theorem 1 and Corollary 2):

• Theorem 1. If M and N are matchings with |M| = r, |N| = s and s > r, then the symmetric difference M ⊕ N contains at least s − r vertex-disjoint augmenting paths relative to M. The proof is a one-line degree argument: in the graph (V, M ⊕ N) every vertex has degree ≤ 2, so every connected component is an isolated vertex, an even alternating cycle, or an alternating path. Assign each component Cᵢ the value δ(Cᵢ) = |Eᵢ ∩ N| − |Eᵢ ∩ M| ∈ {−1, 0, 1}, note that δ(Cᵢ) = 1 exactly when Cᵢ is an M-augmenting path, and observe Σ δ(Cᵢ) = |N| − |M| = s − r.
• Corollary 2. Consequently, if |M| = r and the maximum is s > r, there is an augmenting path relative to M of length at most 2⌊r/(s − r)⌋ + 1. Reason: the s − r disjoint augmenting paths jointly use at most r edges of M, so one of them uses at most ⌊r/(s − r)⌋ of them, and an augmenting path with k matched edges has 2k + 1 edges in total.

Corollary 2 is the whole of §6 in embryo: when you are far from optimal, a short augmenting path is guaranteed to exist, so a search that finds shortest paths first makes fast progress early and only has to work hard near the end.

Concretely: in §2, suppose we’ve greedily set M = {(u₁,p₁), (u₃,p₂), (u₄,p₃)} (size 3, with u₂ and p₄ free). Search from u₂: u₂ → p₁ (unmatched edge) → u₁ (via matched edge (u₁,p₁)) → p₂ (unmatched) → u₃ (via matched (u₃,p₂)) → p₃ (unmatched) → u₄ (via matched (u₄,p₃)) → p₄ (unmatched, free).

This is an augmenting path: u₂ — p₁ — u₁ — p₂ — u₃ — p₃ — u₄ — p₄. Flip the edges: M_new = {(u₂,p₁), (u₁,p₂), (u₃,p₃), (u₄,p₄)} — the matching of size 4 we found by inspection.

This gives a clean algorithm: repeatedly find augmenting paths (via DFS or BFS from free L-vertices) until none exist.

4. Algorithm 1 — Reduction to Max Flow

The cleanest theoretical approach is to translate MBM into a max-flow instance. Given bipartite G = (L ∪ R, E):

1. Add a super-source s and a super-sink t.
2. For every u ∈ L, add edge s → u with capacity 1.
3. For every v ∈ R, add edge v → t with capacity 1.
4. For every original edge (u, v) ∈ E, add directed edge u → v with capacity 1.
5. Compute the maximum s → t flow f.

Claim. |f| = size of max matching. The matching M is recovered as M = {(u, v) : f(u, v) = 1}.

Why this works.

• Capacity 1 on left-edges (s → u): ensures each left-vertex sends at most 1 unit of flow, hence appears in at most 1 chosen edge.
• Capacity 1 on right-edges (v → t): ensures each right-vertex receives at most 1 unit, hence appears in at most 1 chosen edge.
• Capacity 1 on the bipartite edges: ensures each edge is either fully used (in the matching) or unused.
• Integrality theorem (Ford-Fulkerson): since all capacities are integers, the max-flow algorithm produces an integer flow, so each edge is exactly 0 or 1. No fractional matching nonsense.
• Max flow = max matching: any matching of size k corresponds to a flow of value k (route each matched edge); any flow of value k decomposes into k edge-disjoint s→t paths (each path = one matched pair). So the optima coincide.

4.1 Worked Reduction

For our §2 example with 4 students and 4 projects, the flow network has:

• s → u₁, s → u₂, s → u₃, s → u₄ — each capacity 1
• u₁ → p₁, u₁ → p₂, u₂ → p₁, u₃ → p₂, u₃ → p₃, u₄ → p₂, u₄ → p₃, u₄ → p₄ — each capacity 1
• p₁ → t, p₂ → t, p₃ → t, p₄ → t — each capacity 1

Running max-flow gives 4 units pushed, with flow on (u₁, p₂), (u₂, p₁), (u₃, p₃), (u₄, p₄) — recovering the matching.

4.2 Pseudocode (Reduction Approach)

bipartite_matching_via_flow(L, R, edges):
    flow_edges := []
    s := new node "source"
    t := new node "sink"
    for each u in L: flow_edges.append((s, u, 1))
    for each v in R: flow_edges.append((v, t, 1))
    for each (u, v) in edges: flow_edges.append((u, v, 1))
    flow := max_flow(flow_edges, s, t)            # any algorithm
    matching := { (u, v) for (u, v) in edges if f(u, v) == 1 }
    return matching

4.3 Python (Reduction Approach)

from collections import defaultdict, deque
 
def bipartite_matching_via_flow(L, R, edges):
    s, t = "_SRC_", "_SNK_"
    cap = defaultdict(lambda: defaultdict(int))
    for u in L:
        cap[s][u] = 1
    for v in R:
        cap[v][t] = 1
    for u, v in edges:
        cap[u][v] = 1
 
    def bfs_path():
        parent = {s: None}
        q = deque([s])
        while q and t not in parent:
            u = q.popleft()
            for v, c in cap[u].items():
                if c > 0 and v not in parent:
                    parent[v] = u
                    if v == t: break
                    q.append(v)
        return parent if t in parent else None
 
    while True:
        p = bfs_path()
        if p is None:
            break
        # bottleneck = 1 always (unit capacities)
        v = t
        while p[v] is not None:
            u = p[v]
            cap[u][v] -= 1
            cap[v][u] += 1
            v = u
 
    # Recover matching: edges (u, v) with flow 1 = original cap minus residual
    matching = []
    for u, v in edges:
        if cap[u][v] == 0 and cap[v][u] == 1:    # forward saturated
            matching.append((u, v))
    return matching

Complexity — and a correction worth making. The complexity is that of the underlying max-flow algorithm, but the generic bound for that algorithm is the wrong number to quote here. Edmonds-Karp’s worst case is O(V · E²) because it bounds the number of shortest-augmenting-path phases by O(V·E) for arbitrary capacities. On this network that bound is enormously pessimistic: the value of the maximum flow is at most min(|L|, |R|) ≤ V/2, every augmentation pushes exactly one unit (all capacities are 1, so the bottleneck is always 1), and therefore there are at most V/2 augmentations, each costing one O(E) BFS. The honest bound for the reduction is O(V · E) — the same as Kuhn’s algorithm in §5, not worse. Hopcroft and Karp say as much in their own introduction: “The best previous methods ([1], [3], [4], [5]) seem to require O(mn) steps” (Hopcroft & Karp 1973), and the Cornell CS6820 notes reach the same O(mn) for the naive augmenting-path algorithm (Cornell CS6820, Matchings). The real gain in §6 comes from doing many augmentations per O(E) sweep, not from beating a quadratic-in-E bound that was never in force.

5. Algorithm 2 — Direct Augmenting-Path (Kuhn’s Algorithm)

The “Hungarian-method-inspired” simple approach skips the max-flow framework and directly hunts augmenting paths via DFS from each free L-vertex. Often called Kuhn’s algorithm in competitive programming circles.

kuhn_matching(L, R, adj):
    match_R := {} (maps each r ∈ R to its matched L-vertex, or None)
    for each u in L:
        visited := empty set
        try_kuhn(u, visited, adj, match_R)
    return match_R

try_kuhn(u, visited, adj, match_R):
    for each v in adj[u]:
        if v in visited: continue
        visited.add(v)
        if match_R[v] is None or try_kuhn(match_R[v], visited, adj, match_R):
            match_R[v] := u
            return True
    return False

The recursion implements augmenting-path search: try_kuhn(u) looks for an alternating path starting at u; if v is free, match it; if v is taken, try to “displace” its current partner by recursively finding that partner an augmenting continuation.

5.1 Python — Kuhn’s

def kuhn_matching(L, R, adj):
    """adj: dict mapping L-vertex to list of R-neighbors. Returns matching dict R→L."""
    match_R = {v: None for v in R}
 
    def try_kuhn(u, visited):
        for v in adj[u]:
            if v in visited:
                continue
            visited.add(v)
            if match_R[v] is None or try_kuhn(match_R[v], visited):
                match_R[v] = u
                return True
        return False
 
    for u in L:
        try_kuhn(u, set())
    return {v: u for v, u in match_R.items() if u is not None}

Complexity. try_kuhn from a single L-vertex is O(V + E) because each R-vertex is visited at most once per call (the visited set guards against revisits). We call it O(|L|) ≤ O(V) times. Total: O(V · (V + E)) = O(V · E).

This is the same asymptotic bound as running Edmonds-Karp on the §4 reduction once you do the unit-capacity accounting properly (see the correction at the end of §4) — the two are conceptually identical, and neither is O(V·E²) here. What Kuhn’s buys you is constant factors and code size: no explicit source, sink, residual graph, or capacity bookkeeping, just an adjacency list and one array match_R. It is the right thing to write on a whiteboard; it is not asymptotically better than the reduction.

Naming caution. “Kuhn’s algorithm” for this DFS routine is competitive-programming folklore (it is the name used by cp-algorithms), and it is not what Kuhn published. Kuhn’s actual 1955 paper is about the weighted assignment problem and works with dual vertex potentials — see §9, where the primary source is read directly. The unweighted DFS above is better described as “repeated augmenting-path search”, which is what Hopcroft and Karp call the prior art they were improving on.

6. Algorithm 3 — Hopcroft-Karp (O(E · √V))

The fastest classical algorithm for unweighted MBM is Hopcroft-Karp (1973). The paper’s own abstract states the bound as “a number of computation steps proportional to (m + n)√n” — i.e. O(E·√V) — and its title, “An n^{5/2} algorithm for maximum matchings in bipartite graphs”, quotes the dense-graph specialisation m = O(n²) (Hopcroft & Karp, SIAM J. Comput. 2(4), 1973, 225–231).

The idea: instead of finding one augmenting path at a time, find a maximal set of vertex-disjoint shortest augmenting paths and augment along all of them at once. The paper calls one such round a phase, and the entire contribution is the observation that phases — not augmentations — are the right unit of accounting.

6.1 The Algorithm, as the Paper States It

Hopcroft and Karp present it in two layers. Algorithm A is graph-agnostic and is where the √ comes from:

Step 0.  M := ∅
Step 1.  let l(M) = length of a shortest augmenting path relative to M
         find a MAXIMAL set of paths {Q₁, …, Q_t} such that
           (a) each Qᵢ is an augmenting path with |Qᵢ| = l(M)
           (b) the Qᵢ are pairwise vertex-disjoint
         halt if no such paths exist
Step 2.  M := M ⊕ Q₁ ⊕ Q₂ ⊕ ⋯ ⊕ Q_t;  go to Step 1

Note “maximal”, not “maximum”: the set must merely be impossible to extend, which is what makes it findable in linear time. The paper spells this out in a footnote — “A set is maximal with a given property if it has the property and is not properly contained in any set that has the property.” Getting this wrong (searching for a maximum disjoint set) turns a linear step into an NP-hard one.

Algorithm B is the bipartite implementation of Step 1. It builds a layered directed graph and then runs a single depth-first search that deletes every edge it touches:

1. Orient the edges so that augmenting paths become directed paths: every edge in E \ M runs R → L, every edge in M runs L → R. (The paper writes X for “boys” and Y for “girls”; the direction convention is theirs.)
2. Layer by BFS. L₀ = the free L-vertices; L_{i+1} = the vertices reachable by one edge from L_i that have not appeared in any earlier layer. Let i* be the smallest index at which a free R-vertex appears. Truncate everything beyond L_{i*}.
3. Property (iv) of the layered graph is the correctness statement: “The shortest augmenting paths relative to M are in one-to-one correspondence with the paths of Ĝ which begin at a free girl and end at a free boy. These paths are all of length i*.”
4. Extract a maximal disjoint set by DFS. Adjoin a source s joined to every free vertex on one side and a sink t from every free vertex on the other, then run a stack-based DFS that deletes each edge as it is processed. Hopcroft and Karp’s own justification of the linear bound is one sentence: “Each while block in the algorithm contains either a POP or a DELETE operation. Since no vertex is POPed more than once, or DELETEd from any LIST more than once, the running time of the algorithm is bounded by a constant times (number of vertices + number of edges).”

So one phase is O(V + E) = O(E) (assuming no isolated vertices), and the only remaining question is how many phases there are.

flowchart LR
  subgraph L0["L₀ — free left vertices"]
    a((u₂))
  end
  subgraph L1["L₁ — their R-neighbours"]
    b((p₁))
  end
  subgraph L2["L₂ — matched L-partners"]
    c((u₁))
  end
  subgraph L3["L₃ — next R-neighbours"]
    d((p₂))
  end
  subgraph L4["L₄"]
    e((u₃))
  end
  subgraph L5["L₅ — free R vertex reached: i* = 5"]
    f((p₄))
  end
  a -->|"unmatched"| b
  b ==>|"matched"| c
  c -->|"unmatched"| d
  d ==>|"matched"| e
  e -->|"unmatched"| f

What this diagram shows. The layered graph Ĝ that one Hopcroft–Karp phase builds, for a small instance. Even layers hold L-vertices, odd layers hold R-vertices; thin arrows are unmatched edges, thick arrows are matched edges, so any source-to-sink path in this graph automatically alternates and is automatically an augmenting path. The insight to take away: the BFS does not search for a path — it computes the distance layering, and i* (the first layer containing a free R-vertex) fixes the length of every augmenting path the subsequent DFS is allowed to use. That fixed length is what makes the paths found in one phase mutually disjoint-able and what makes the phase counter monotone.

6.2 Why O(√V) Phases — the Argument, Done Correctly

This is the step most write-ups garble, so here it is in full. Two facts do the work.

Fact 1 — the shortest augmenting-path length strictly increases every phase. Hopcroft & Karp’s Theorem 2 states that if P is a shortest augmenting path relative to M and P′ is an augmenting path relative to M ⊕ P, then |P′| ≥ |P| + |P ∩ P′|. Their Corollaries 3 and 4 turn this into: the sequence of augmenting-path lengths is non-decreasing, and all paths of equal length are vertex-disjoint — hence the computation is partitioned into phases, each with its own strictly larger path length. The Cornell CS6820 notes prove the same monotonicity directly on the layered graph (Cornell CS6820, Lemma 6).

Fact 2 — a long shortest path means you are nearly done. This is Corollary 2 from §3 read backwards. If M* is maximum and k = |M*| − |M|, then M ⊕ M* contains k vertex-disjoint augmenting paths; k disjoint subgraphs cannot each have more than V/k vertices, so some augmenting path has fewer than V/k vertices. Contrapositive: if the shortest augmenting path has length ≥ √V, then k < √V.

Combine them. After √V phases the shortest augmenting path exceeds √V (Fact 1), so at most √V augmentations remain (Fact 2), and each remaining phase performs at least one — giving fewer than 2√V phases and a total of O(E√V).

The common mis-statement

Many summaries — including an earlier revision of this note — write the second half as “the remaining augmenting paths are vertex-disjoint, so at most V/√V = √V more phases suffice.” That is not the argument: disjointness holds inside M ⊕ M*, not among the paths a future phase will find, and the bound comes from counting vertices across the k disjoint paths of M ⊕ M*, not from disjointness of future phases. The conclusion is right; the reasoning as usually stated does not support it.

Hopcroft and Karp themselves phrase the bound in terms of the size s of the maximum matching rather than V. Their Theorem 3 shows the number of distinct augmenting-path lengths in the sequence |P₀|, …, |P_{s−1}| is at most 2⌊√s⌋ + 2, and Corollary 5 concludes that Algorithm A terminates within 2⌊√s⌋ + 2 executions of Step 1. Since s ≤ V/2, 2⌊√s⌋ + 2 ≤ 2⌊√(V/2)⌋ + 2 = O(√V); quoting the bound in terms of s is tighter and is what the paper actually proves.

For full implementation and discussion, see Hopcroft-Karp. In an interview, the O(E√V) bound plus “phases of vertex-disjoint shortest augmenting paths, and the path length strictly increases each phase” is the answer.

6.3 Hopcroft-Karp and Dinic’s Algorithm — Who Anticipated Whom

It is standard, and correct, to say that Hopcroft-Karp is Dinic’s Algorithm specialised to bipartite unit-capacity networks: a phase is a blocking flow in a level graph. It is not correct to say Hopcroft-Karp “anticipated” Dinic. Dinitz’s blocking-flow algorithm was published in 1970 (Soviet Math. Doklady), three years before Hopcroft-Karp, and was simply unknown in the West at the time; the two were arrived at independently. Even and Tarjan later showed that Dinic’s algorithm run on a unit-capacity network terminates in O(E√V) for exactly the reason above, which is how the two results were finally recognised as the same theorem. Note also the honest scoping: the √ phase bound is a property of unit-capacity networks, not of Dinic’s algorithm generically — on general capacities Dinic is O(V²E).

Uncertain

Verify: the 1970 publication date and venue for Dinitz’s blocking-flow algorithm, and the exact statement of the Even–Tarjan unit-capacity bound. Reason: neither the Dinitz 1970 Doklady note nor Even & Tarjan (1975) was retrievable from this machine — every mirror tried returned 404. The claim is corroborated indirectly by Micali & Vazirani 1980, whose historical note credits the O(√|V|)-phases idea to Hopcroft and Karp and the O(|V|^{2.5}) general-graph bound to Even and Kariv, but does not date Dinitz. To resolve: obtain Dinitz (1970) or Even & Tarjan, “Network flow and testing graph connectivity”, SIAM J. Comput. 4 (1975).

7. König’s Theorem (Min Vertex Cover = Max Matching for Bipartite)

A vertex cover is a set of vertices C such that every edge has at least one endpoint in C. The minimum vertex cover problem is generally NP-hard, but for bipartite graphs it is polynomial due to König’s theorem.

Theorem (König, 1931). In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Diestel states it in exactly this form as Theorem 2.1.1 — “The maximum cardinality of a matching in G is equal to the minimum cardinality of a vertex cover of its edges” — and gives a proof that needs no flow theory at all (Diestel, Graph Theory, Ch. 2). Take a maximum matching M; from each matched edge pick its R-end if some alternating path ends at that vertex, and its L-end otherwise. That gives a set U of exactly |M| vertices, and the argument that U covers every edge is three lines: if ab ∈ E with a ∉ U, then either a is free (so ab itself is an alternating path ending at b) or a is matched to some b′ with an alternating path ending at b′, which extends to one ending at b; either way b ∈ U. Since any vertex cover must cover M itself, no cover can be smaller than |M|.

Kuhn describes reading exactly this theorem in König’s 1936 book Theorie der endlichen und unendlichen Graphen as the moment the Hungarian method became possible, and adds the appraisal that matters here: “It is first of all an example of linear programming duality proved some decades before Dantzig had formulated linear programming. It is also the first example of a problem in combinatorial optimization that was solved by a constructive polynomial time algorithm laid out by König” (Kuhn 2012, A tale of three eras). In the matrix language König used, the statement reads: given a square 0–1 matrix, the maximum number of ones no two of which share a row or column equals the minimum number of lines (rows or columns) needed to cover all the ones.

Independently, it is also a corollary of Min-Cut Max-Flow Theorem: run max-flow on the §4 reduction, take a minimum cut S, and read the cover off it. Trevisan gives the construction explicitly — with L₁ = L ∩ S, L₂ = L \ S, R₁ = R ∩ S, R₂ = R \ S, and B the vertices of R₂ having a neighbour in L₁, the set C = L₂ ∪ R₁ ∪ B is a vertex cover whose size equals the cut capacity |L₂| + |R₁| + edges(L₁, R₂) ≥ |C|, hence equals the maximum matching (Trevisan, CS261 Lecture 14, Claims 6–7). The cut’s “either drop a source edge s → u or a sink edge v → t” structure is precisely “put u or v in the cover”.

flowchart TB
  MBM["max matching |M|<br/>(primal: pack edges)"]
  MVC["min vertex cover |C|<br/>(dual: hit every edge)"]
  MF["max s→t flow<br/>on the §4 unit-capacity network"]
  MC["min s→t cut"]
  HALL["Hall's condition<br/>|N(A)| ≥ |A| for all A ⊆ L"]
  MBM -->|"König 1931"| MVC
  MBM -->|"integrality of unit-capacity flow"| MF
  MF -->|"Ford–Fulkerson MFMC 1956"| MC
  MC -->|"Trevisan's C = L₂ ∪ R₁ ∪ B"| MVC
  MBM -->|"saturates L exactly when"| HALL
  MVC -->|"small cover yields a violator"| HALL

What this diagram shows. Four statements that are all the same theorem seen from four angles, and the named result that converts each into the next. The insight to take away: you never have to choose between “the flow proof” and “the combinatorial proof” — they are two traversals of this square, and the practical consequence is that whichever object your algorithm already computes (a matching, a flow, a cut) hands you the other three for free. That is why §7’s four-line recipe and §8’s Hall violator both fall out of a single run of Hopcroft–Karp with no extra work.

Constructive recipe (turning a max matching into a min vertex cover):

1. Let M be a max bipartite matching.
2. Let U = set of unmatched L-vertices.
3. Let Z = set of vertices reachable from U via alternating paths.
4. Min vertex cover C = (L \ Z) ∪ (R ∩ Z). Size: |L \ Z| + |R ∩ Z| = |M|.

(Verifying that C is a valid vertex cover and has size |M| is a satisfying exercise; see Lovász & Plummer’s Matching Theory (1986) for full detail.)

Why König’s theorem is special. Min vertex cover is NP-hard for general graphs (it appears as “node cover” among Karp’s 21 original NP-complete problems, 1972). For bipartite graphs, König’s theorem makes it polynomial-time. Bipartiteness is the crucial structural feature exploited by LP duality / total unimodularity. Berge put his finger on exactly this in 1957 when he wrote that “the linear programming duality used by H. Kuhn no longer subsists when the graph is not bipartite” (Berge 1957) — the min-max relation between matching and cover simply fails on, say, a triangle, where the maximum matching has size 1 and the minimum vertex cover has size 2. This is one of the cleanest examples of how a structural hypothesis collapses hardness.

A history footnote worth having. König’s 1931 result is not quite as isolated as textbooks make it look: it is the bipartite case of a more general theorem attributed to Menger (1927), which Menger’s original proof had missed. Diestel’s chapter notes record that “when Menger showed König his theorem and proof during a visit to Budapest in 1930, they seem to have noticed this gap. König published his proof in two papers of 1931 and 1933, and quotes Menger as claiming to have settled this case independently” (Diestel, Ch. 2 notes). Kuhn also insists — and it is worth honouring — that Kőnig’s name carries a Hungarian double acute, not a German umlaut; he cites a letter from Kőnig himself asserting the correct spelling (Kuhn 2012). This note writes “König” throughout because that is the form every algorithms textbook uses, but the accent is wrong.

8. Hall’s Marriage Theorem

A perfect matching of L is a matching that covers every L-vertex (so |L| ≤ |R|).

Theorem (Hall, 1935). A bipartite graph (L, R) has a perfect matching of L if and only if for every subset A ⊆ L, |N(A)| ≥ |A|, where N(A) is the set of R-neighbors of any vertex in A.

Diestel states it as Theorem 2.1.2 — “G contains a matching of A if and only if |N(S)| ≥ |S| for all S ⊆ A” — and, tellingly, gives three proofs “of rather different character”, which is a fair index of how central it is. His chapter notes add the historical judgement: “At the time, neither of these results [König’s and Menger’s] was nearly as well known as Hall’s marriage theorem, which he proved even later, in 1935. To this day, Hall’s theorem remains one of the most applied graph-theoretic results” (Diestel, Ch. 2).

The condition is called Hall’s condition (“the neighborhood of every subset is at least as big as the subset”). Necessity is obvious — if some A has |N(A)| < |A|, you cannot match all of A into distinct neighbors. Sufficiency follows from MFMC by checking the bipartite-flow reduction has no “tight” cut smaller than |L|; equivalently it follows from König, since a cover of size < |L| can be rearranged into a violating set.

Hall’s theorem is the certificate half of the algorithm, and this is the part usually skipped. When MBM terminates with a matching of size < |L|, you do not merely learn “no augmenting path was found” — you can hand back an explicit witness. Take Z = the set of vertices reachable from unmatched L-vertices by alternating paths (the same Z as the König recipe above); then A = L ∩ Z satisfies |N(A)| = |R ∩ Z| < |A|, because every vertex of R ∩ Z is matched (otherwise there is an augmenting path) and its partner lies in A, while A additionally contains the unmatched L-vertices. Trevisan derives exactly this set and concludes “we have found a set on the left that is bigger than its neighborhood” (Trevisan, CS261 L14). Practically: if you are writing an assignment service, this is the difference between telling an operator “no full assignment exists” and telling them “these six shifts collectively have only five qualified staff between them” — the second is actionable, costs nothing extra to compute, and is the single most useful thing a matching component can log.

Hall’s condition is not a cheap test. It quantifies over all 2^{|L|} subsets, so it is a characterisation, not an algorithm. You verify it by running a matching algorithm, never the other way round. The one place the raw condition earns its keep is in proofs and in structured instances — e.g. Diestel’s Corollary 2.1.3 (every k-regular bipartite graph has a perfect matching, since regularity makes Hall’s condition automatic by edge counting), which in turn yields Petersen’s 1891 theorem that every regular graph of positive even degree has a 2-factor.

Uncertain

Verify: the exact statement and pagination of Hall’s original 1935 paper, “On Representatives of Subsets”, J. London Math. Soc. 10 (1): 26–30. Reason: the original was not retrievable from this machine — four candidate mirrors returned 403/404, and JSTOR is inaccessible. The theorem statement above is taken from Diestel’s textbook (read directly) and the bibliographic entry from the bibliography of Kuhn 1955, which lists it as [4] Hall, P., "On Representatives of Subsets," J. London Math. Soc. 10 (1935) 26-30. To resolve: obtain the LMS original or the Hall volume of collected works. Same caveat applies to König (1931) and Egerváry (1931), both of which are cited here only through Kuhn’s bibliography and Diestel’s notes.

9. Weighted Bipartite Matching (the Assignment Problem)

When edges carry weights and you want a perfect matching of extremal total weight, the problem is the assignment problem and the canonical solver is the Hungarian method. This section is worth reading even if you only ever need the unweighted case, because the Hungarian method is where the duality of §7 becomes an algorithm rather than a theorem, and because its history is a small masterpiece of independent rediscovery.

9.1 What Kuhn Actually Published

Kuhn’s paper opens with the problem in its personnel form — “Assuming that numerical scores are available for the performance of each of n persons on each of n jobs, the ‘assignment problem’ is the quest for an assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible” — and states its own provenance in one sentence that explains the name: “One interesting aspect of the algorithm is the fact that it is latent in work of D. König and E. Egerváry that predates the birth of linear programming by more than 15 years (hence the name, the ‘Hungarian Method’).” (Kuhn, Naval Research Logistics Quarterly 2 (1955) 83–97).

The two-part structure of the paper is the two-part structure of the algorithm, and Kuhn says which half came from whom:

• §2, the Simple Assignment Problem — the 0–1 case, “is person i qualified for job j?”, solved by exactly the augmenting-path search of §5 of this note. Kuhn notes it is “derived from the proof of König in ‘Theorie der Graphen’ (1936) Chelsea, 1950, pp. 232-233”.
• §3, the reduction — showing that the general real-weighted problem reduces to a sequence of 0–1 problems by maintaining dual vertex potentials uᵢ (on persons) and v_j (on jobs) with uᵢ + v_j ≥ r_{ij}, and treating an edge as “qualified” exactly when the dual constraint is tight (uᵢ + v_j = r_{ij}). This half Kuhn credits to Egerváry, whose 1931 paper he had translated from Hungarian himself in 1953 for the ONR Logistics Project. Kuhn’s later assessment: “Egerváry, as an expert in matrix theory, generalized König’s result from 0–1 matrices to arbitrary real matrices, giving a constructive proof.”

The mechanism, in one paragraph: maintain a cover (u, v) that is feasible (uᵢ + v_j ≥ r_{ij} everywhere) together with a matching that uses only tight edges. Run augmenting-path search on the tight subgraph. If it succeeds, the matching grows by one. If it fails, the failed search has exposed a set of reachable vertices; decrease uᵢ on the reachable persons and increase v_j on the reachable jobs by the smallest slack min(uᵢ + v_j − r_{ij}) across the frontier, which creates at least one new tight edge without ever destroying feasibility. Kuhn’s own termination argument is exactly this pair of monotone quantities: “Since the number of assignments is bounded from above by n and the covering sums are bounded from below by zero, this insures the termination of the combined algorithm.” At the end, primal and dual objectives coincide — Kuhn’s worked example finishes with r₁₁ + r₂₃ + r₃₄ + r₄₂ = 8 + 7 + 9 + 3 = 27 and u₁ + ⋯ + u₄ + v₁ + ⋯ + v₄ = 7 + 5 + 6 + 3 + 1 + 0 + 2 + 3 = 27. That equality is the optimality certificate, and it is König’s theorem carrying weights.

9.2 The Complexity, Told Honestly

The claim “the Hungarian algorithm is O(n³)” is true of the algorithm as we run it today and false of both 1950s papers. Getting this right requires separating what was proved from what is now known:

Source	What it actually claims	Elementary-operation reading
Kuhn 1955	Termination only — assignments bounded above by n, covering sums bounded below by 0. No running-time bound is stated anywhere in the paper.	—
Munkres 1957	“The final maximum on the number of operations needed is (11n³ + 12n² + 31n)/6”, where an “operation” is scan a line, cover or uncover a line, add to or subtract from a line, star or unstar a zero, prime or unprime a zero	each line operation touches n cells, so Θ(n³) line operations is Θ(n⁴) element accesses
Edmonds & Karp 1972	“algorithm solves the n × n assignment problem in O(n³) steps” — shortest augmenting paths with Johnson-style potential reweighting	genuinely O(n³)

So the first explicit polynomial bound is Munkres’, and the first genuine O(n³) is Edmonds and Karp’s (Munkres, J. SIAM 5(1), 1957, 32–38; Edmonds & Karp, JACM 19(2), 1972). Munkres also records the comparison that made the result feel like a result at the time: his bound “is of theoretical interest, since it is so much smaller than the n! operations necessary in the most straightforward attack on the problem.” Citing “Kuhn 1955, Munkres 1957, O(V³)” as one undifferentiated fact — as an earlier revision of this note did — silently back-dates a 1972 bound by fifteen years.

9.3 Jacobi Got There First, in Latin, Before 1851

The best story in this area, and one almost no algorithms course tells. In 2005 François Ollivier, working on bounds for systems of differential equations, wrote to Kuhn about two old Latin papers of Jacobi: “Two years ago I began to study two old papers in Latin by Jacobi. These are related to a conjectural bound expressed by solving the Assignment Problem with a matrix h_{ij} the order of variable j in equation i. Jacobi gave a polynomial algorithm to compute the bound. What is its relation to the Hungarian Method?”

Kuhn worked through the correspondence and answered flatly: “we can conclude that the algorithms are the same, just expressed in different terms!” The mapping is exact — Jacobi’s underlined column maxima are the algorithm’s zeros, his covers and choices are König’s covers and asterisked choices, and “the dual variables u are the negatives of the amounts that Jacobi adds to the rows to create new column maxima” (Kuhn 2012, A tale of three eras: The discovery and rediscovery of the Hungarian Method, EJOR 219, 641–651).

The dating is easy to garble, so here it is precisely. The paper is De investigando ordine systematis aequationum differentialium vulgarium cujuscunque, published posthumously by C. W. Borchardt in Journal für die reine und angewandte Mathematik Bd. 64, pp. 297–320, and reprinted in Jacobi’s Gesammelte Werke (Reimer, 1890, pp. 193–216) — the edition Ollivier translated from the Latin (Ollivier’s English translation; Ollivier, Jacobi’s bound and normal forms computations: a historical survey, arXiv:0911.2674; Ollivier’s Jacobi page at LIX). Jacobi died in 1851, so the work predates Kuhn’s paper by more than a century. Kuhn’s own explanation of why nobody noticed: “Jacobi was attempting to establish a bound on the degree of a system of differential equations and discovered the mathematical problem that is the Assignment Problem in the course of this research. The fact that he discovered a good algorithm for calculating this bound is thoroughly modern and out of context in the 19th century.”

timeline
    title Four independent discoveries of one algorithm
    Before 1851 (pub. 1865 and 1890) : Jacobi - polynomial algorithm for a differential-equation order bound; identical to the Hungarian method; in Latin, posthumous
    1931 : Konig - bipartite min-cover equals max-matching, constructively, decades before linear programming
    1931 : Egervary - generalises Konig from 0-1 matrices to arbitrary real matrices, constructively
    1955 : Kuhn - reads Konig's 1936 book plus his own translation of Egervary, assembles the Hungarian Method
    1957 : Munkres - first explicit operation count, (11n^3 + 12n^2 + 31n)/6 line operations
    1972 : Edmonds and Karp - first genuine O(n^3), via shortest augmenting paths with potentials
    2005 : Ollivier finds Jacobi's version; Kuhn confirms the algorithms are the same

What this diagram shows. The same algorithm reached four times, in four languages and four research programmes, across more than 160 years. The insight to take away: the Hungarian method is not a clever trick somebody invented but the natural algorithm for a min-max duality — anyone who needs the dual of a bipartite packing problem and is willing to iterate will find it. That is also why it is worth learning as “primal-dual augmenting search with vertex potentials” rather than as a matrix-crossing-out recipe: the recipe is the 1955 presentation, the potentials are the idea.

9.4 Practical Guidance

For the case where you want maximum-cardinality matching but, among such matchings, prefer minimum (or maximum) weight, the same framework applies; you can equally reduce to min-cost max-flow. See Hungarian Algorithm for the implementation, and note §12.9 on why a naive min-cost-flow reduction with negative weights needs Bellman-Ford or Johnson-style potentials before you may use Dijkstra’s Algorithm.

10. Beyond Bipartite — Blossoms and Micali–Vazirani

Everything above leans on bipartiteness in one specific place: in a bipartite graph, every alternating path from a given free vertex to a given vertex has a fixed parity, because the two sides alternate. Drop that and augmenting-path search breaks, because a search can reach the same vertex by both an even-length and an odd-length alternating path. Vazirani states the split exactly this way: “Whereas in the former case, all alternating paths from an unmatched vertex f to a matched vertex v must have the same parity, even or odd, in the latter they can be of both parities. Edmonds defined the key notion of blossoms and finessed this difficulty in non-bipartite graphs by ‘shrinking’ blossoms” (Vazirani 2013, arXiv:1210.4594).

Berge’s theorem (§3) is already general — it never assumed bipartiteness — so the characterisation of optimality survives untouched; only the search does not.

The lineage, taken from the historical note in the Micali–Vazirani paper itself (read by rendering the scanned FOCS proceedings page as an image, since the PDF carries no extractable text):

Year	Result	Bound
1957	Berge — a matching is maximum iff no augmenting path exists	—
1965	Edmonds, Paths, trees, and flowers — blossom shrinking; first polynomial general matching	O(V⁴)
1973	Hopcroft & Karp — bipartite only	O(E√V)
1975	Even & Kariv — general graphs	O(V^{2.5})
1980	Micali & Vazirani — general graphs, matching the bipartite bound	O(E√V)

Micali and Vazirani’s own abstract describes the trick that made it work: “Our contribution consists in devising a special way of handling blossoms… When it detects the presence of a blossom, it does not ‘shrink’ the blossom immediately. Instead, it delays the shrinking in such a way that the first augmenting path found is of minimum length.” Their historical note credits the phase structure directly upstream: “As shown by Hopcroft and Karp, only O(√|V|) such phases are needed for finding a maximum matching” (Micali & Vazirani, 21st Annual Symposium on Foundations of Computer Science, IEEE 1980, p. 17).

The running-time caveat that nearly every summary omits. MV80’s O(m√n) claim rested on an unproven assumption about a data-structure task. Vazirani’s 2013 paper — by one of the two authors — sets the record straight: “The paper [MV80] had claimed a running time of O(m√n), on the pointer model… However, this was based on an unproven claim that a certain datastructure task could be accomplished in linear time… The current status is that the MV algorithm achieves a running time of O(m√n · α(m,n)) on the pointer model (using Tarjan’s set union algorithm), where α is the inverse Ackermann function, and O(m√n) on the RAM model (using Gabow and Tarjan’s linear time algorithm for a special case of set union).” The inverse-Ackermann factor is therefore a pointer-machine artefact of the union-find, not a property of a “Gabow variant of the blossom algorithm” — an earlier revision of this note attributed O(E·V·α(V)) to Gabow, which conflates two different things and gets the exponent wrong besides.

For dense graphs there are small improvements — O(m√(n·log(n²/m))/log n), and O(n^ω) via fast matrix multiplication with a large constant — but Vazirani’s summary judgement stands: “For all practical purposes, the Micali-Vazirani [MV80] general graph maximum matching algorithm is still the most efficient known algorithm for the problem.”

Practical takeaway. If you can verify bipartiteness (Bipartite Check is a linear-time BFS 2-colouring), do so and use Hopcroft–Karp. Reach for blossom only when the graph genuinely has odd cycles — the classic case being a one-sided pairing problem such as pairing players into teams, roommate assignment, or kidney-exchange cycles, where there is no natural left/right split at all. (Note that the one-sided pairing problem with preferences is a different beast again: stable roommates, where existence itself can fail — see Stable Matching.) See Edmonds’ Blossom Algorithm.

11. Common Interview Problems

Problem	Pattern
LC 1947 — Maximum Compatibility Score Sum	Weighted bipartite matching → Hungarian / DP / brute force (small)
LC 1820 — Maximum Number of Accepted Invitations	Plain MBM
LC 1349 — Maximum Students Taking Exam	Bipartite matching on grid (or bitmask DP)
LC 1066 — Campus Bikes II	Weighted bipartite matching → bitmask DP for small inputs
LC 1879 — Minimum XOR Sum of Two Arrays	Bitmask DP equivalent to assignment problem
LC 1203 — Sort Items by Groups Respecting Dependencies	Topological sort, not strictly matching
Classic: workers-to-jobs assignment	Hungarian algorithm
Classic: stable marriage	Gale-Shapley — a different problem, see Stable Matching
Classic: Maximum Edge-Disjoint Paths	Reduce to max-flow with unit capacities
Classic: Latin square completion	König’s theorem + bipartite matching

For a typical “match these to those” interview question, the right tool is:

• Equal-cardinality, must-be-perfect-matching, no weights: Hopcroft-Karp or Kuhn’s.
• Maximum-cardinality, no weights: Same as above.
• Weights, minimize total cost: Hungarian algorithm.
• Online / streaming: algorithmic deepwater; may be approximation only.

12. Pitfalls

12.1 “Maximal” vs “Maximum” Matching

A maximal matching is one that cannot be extended by adding any single edge — a local optimum reachable greedily in O(E). A maximum matching is the globally largest. Maximal can be much smaller than maximum (e.g., a path of length 4: greedy picks the middle edge → maximal of size 1; max is 2). Always verify which is needed.

12.2 Forgetting the “visited” Guard in Kuhn’s

Without visited, try_kuhn can recurse infinitely cycling between two R-vertices that keep displacing each other. The set ensures each R-vertex is considered at most once per outer try_kuhn(u) call.

12.3 Reusing the visited Set Across Outer Iterations

The visited set must be fresh per outer iteration (per starting L-vertex). If reused, later vertices will erroneously skip available R-vertices.

12.4 Mistaking the Matching for the Cover or Vice Versa

The matching is a set of edges; the vertex cover is a set of vertices. They have the same size for bipartite (König) but are different objects. Be precise about which the problem asks for.

12.5 Treating the Graph as Bipartite Without Verification

If the input graph isn’t bipartite, the algorithms above do not apply — general matching needs Edmonds’ Blossom Algorithm (O(V⁴) as Edmonds published it in 1965) or Micali-Vazirani (O(E√V)). Always verify with Bipartite Check (BFS 2-coloring) first if there is any doubt; see §10 for the full picture.

12.6 Building the Wrong Reduction

Common errors:

• Adding edges from R back to L (creates cycles in the flow network — incorrect).
• Capacities other than 1 (creates fractional flows — incorrect).
• Forgetting the source/sink completely (no max-flow problem to solve).

The standard recipe in §4 is: s → L (capacity 1), L → R (capacity 1, only on edges), R → t (capacity 1).

12.7 Confusing With Non-Bipartite Matching

General-graph maximum matching is solvable by Edmonds’ blossom algorithm — O(V⁴) as published in 1965, per the historical note in Micali & Vazirani 1980 — and by Micali–Vazirani in O(E√V) on the RAM model. The frequently-repeated figures “O(V³) for blossom” and “O(E·V·α(V)) with Gabow” are both garbled; §10 gives the sourced versions. Either way the algorithm is significantly more complex than the bipartite case because of odd-cycle “blossoms”. Don’t reach for blossom unless bipartiteness is genuinely violated.

12.8 Implicit Assumption of |L| = |R|

MBM works fine when |L| ≠ |R|; the maximum matching is bounded by min(|L|, |R|). A perfect matching requires |L| = |R| and Hall’s condition.

12.9 Negative Cycles in Min-Cost Bipartite Matching

If you reduce weighted MBM to min-cost flow naively, negative-cost edges can create issues for Dijkstra’s Algorithm-based min-cost flow. Use Bellman-Ford for the first augmentation, then potentials (Johnson-style reweighting), then Dijkstra. Or just use the Hungarian algorithm directly.

13. Diagram — Augmenting Path Flip

flowchart LR
  subgraph Before["Before: 3 matched edges"]
    direction LR
    u1((u1)) ===|"M"| p1((p1))
    u2((u2)) -.- p1
    u3((u3)) ===|"M"| p2((p2))
    u4((u4)) ===|"M"| p3((p3))
    u4 -.- p4((p4))
    u3 -.- p3
    u1 -.- p2
  end

flowchart LR
  subgraph After["After: 4 matched edges (flipped along augmenting path u2-p1-u1-p2-u3-p3-u4-p4)"]
    direction LR
    u1((u1)) ===|"M"| p2((p2))
    u2((u2)) ===|"M"| p1((p1))
    u3((u3)) ===|"M"| p3((p3))
    u4((u4)) ===|"M"| p4((p4))
    u1 -.- p1
    u3 -.- p2
    u4 -.- p2
    u4 -.- p3
  end

What these diagrams show. Bold double-line edges are matched (in M); thin dotted edges are unmatched. The “Before” matching has 3 edges, with u₂ and p₄ free. The augmenting path from u₂ (free) to p₄ (free) alternates dotted, bold, dotted, bold, dotted, bold, dotted — it has 7 edges, 4 of them dotted (unmatched) and 3 bold (matched). When we flip edges along the path (change dotted→bold and bold→dotted), the 4 dotted edges become 4 matched edges, and the 3 bold edges become 3 unmatched. The net effect is a matching of size 3 − 3 + 4 = 4. The free endpoints u₂ and p₄ become matched. This single graphical operation is the essence of every bipartite-matching algorithm — they differ only in how efficiently they find these augmenting paths.

14. History and Significance

timeline
    title A century of bipartite matching, with the results verified against primaries
    Before 1851 : Jacobi discovers the assignment algorithm while bounding the order of a differential system; published posthumously, in Latin, and lost to the field until 2005
    1891 : Petersen - every regular graph of positive even degree has a 2-factor; later re-derived in three lines from Hall
    1927 : Menger's theorem, whose bipartite case Menger's own proof misses
    1931 : Konig proves min vertex cover equals max matching for bipartite graphs; Egervary generalises to real matrices
    1935 : Hall's marriage theorem - the subset condition characterising when L can be saturated
    1955 : Kuhn assembles Konig plus Egervary into the Hungarian Method for the weighted problem
    1956 : Ford and Fulkerson prove max-flow min-cut; Konig becomes a corollary
    1957 : Berge - a matching is maximum iff there is no augmenting path, in general graphs
    1965 : Edmonds - blossom shrinking, first polynomial general-graph matching, O(V^4)
    1970 : Dinitz publishes blocking flows in Soviet Math. Doklady, unknown in the West
    1972 : Edmonds and Karp give the first genuine O(n^3) assignment algorithm
    1973 : Hopcroft and Karp - phases of vertex-disjoint shortest augmenting paths, O(E sqrt V)
    1975 : Even and Kariv - O(V^2.5) for general graphs
    1980 : Micali and Vazirani - O(E sqrt V) for general graphs, matching the bipartite bound
    1990 : Karp, Vazirani and Vazirani - RANKING is 1 - 1/e competitive for online bipartite matching, and that is optimal
    2013 : Vazirani publishes the first complete correctness proof of the MV algorithm and corrects its running-time claim
    2022 : Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva - max-flow in m^(1+o(1)) time, giving an almost-linear bipartite matching algorithm

What this diagram shows. The problem’s timeline, restricted to results whose primary source was read while writing this note. The insight to take away: the structure theorems (König, Hall, Berge) all landed decades before the algorithms that exploit them, and every subsequent algorithmic advance is a better way of finding the objects those theorems guarantee. Notice also how much of the sequence is rediscovery rather than discovery — Jacobi in the 1840s, Menger and König tripping over the same theorem in 1930, Dinitz and Hopcroft–Karp arriving at blocking flows independently on opposite sides of the Iron Curtain.

Two corrections to the folklore version of this timeline, both established in the sections above:

• Hopcroft-Karp did not “anticipate” Dinic’s algorithm. Dinitz’s blocking-flow method was published in 1970, three years earlier; the two were independent, and Even and Tarjan later showed Dinic on a unit-capacity network gives the same O(E√V) (see §6.3, which carries an uncertainty flag on the Dinitz citation).
• The Hungarian method is not Kuhn’s invention in any strong sense, and he says so himself. He named it for König and Egerváry deliberately; Jacobi had the same algorithm a century earlier (§9.3).

The fact that bipartite matching has been studied for nearly two centuries, with multiple distinct algorithmic paradigms (LP duality, augmenting paths, blocking flows, push-relabel, randomised algebraic methods, and now interior-point/dynamic-data-structure methods), reflects how foundational the problem is.

15. Open Questions and Recent Developments

• What is the exact lower bound for MBM? For adjacency-matrix input, Ω(V²) is forced simply by reading the input. For sparse graphs, the gap between O(E√V) and an O(E)-ish lower bound remains open. Note the bound quoted throughout this note is 2⌊√s⌋ + 2 phases in terms of the matching size s, which is tighter than the √V form whenever the maximum matching is small.
• Do the recent max-flow breakthroughs translate to bipartite matching? Yes, and the authors say so directly. Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva give an algorithm computing exact max-flow and min-cost flow “on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m^{1+o(1)} time”, and list among its consequences an “m^{1+o(1)} time algorithm for the bipartite matching problem” (arXiv:2203.00671). The same paper’s related-work section places Mądry’s line of results at m^{4/3+o(1)} U^{1/3} for bipartite matching and unit-capacity maxflow. These are not yet competitive in practice — the m^{o(1)} factor hides a formidable dynamic data structure — so Hopcroft–Karp remains what you implement.
• Online bipartite matching — settled ratio, unsettled proofs. The RANKING algorithm of Karp, Vazirani and Vazirani (STOC 1990) achieves competitive ratio 1 − 1/e ≈ 0.632, and no online algorithm can beat it, so the ratio is tight. The proofs, however, needed repair twice. Birnbaum and Mathieu gave the standard simple proof of the 1 − 1/e lower bound, opening with the observation that they “provide a simple proof of their result” precisely because the original was not (Birnbaum & Mathieu, SIGACT News 2008). The upper bound waited longer: Xu’s 2025 paper reports that the original argument “contains several inaccuracies, including a fundamental technical gap in the treatment of the underlying discrete process”, and reconstructs it as a discrete-time death process yielding the sharper bound ⌈n(1 − 1/e) + 2 − 1/e⌉ on the expected number of matched vertices (Xu, arXiv:2503.09530v2, November 2025). The headline number survived; the derivation did not. This is a useful reminder that “the KVV bound” is a claim about a 35-year-old proof, not only about a constant.
• Does the MV data-structure gap ever close on the pointer model? Vazirani reports that “a very recent result [PV13] shows that the avenue suggested in [MV80] for proving this claim will not work” (arXiv:1210.4594), leaving O(m√n·α(m,n)) as the pointer-model status quo. Open whether the α can be removed there.

16. See Also

• Maximum Flow — the framework MBM reduces to
• Edmonds-Karp — O(V·E²) max-flow, sufficient for MBM but suboptimal
• Dinic’s Algorithm — O(V²·E) general, O(E·√V) on unit-capacity (bipartite!)
• Hopcroft-Karp — Dinic’s specialized to bipartite matching
• Hungarian Algorithm — weighted bipartite matching
• Min-Cut Max-Flow Theorem — gives König’s theorem as a corollary
• Bipartite Check — verify the graph is bipartite before applying these
• Breadth-First Search — used in Hopcroft-Karp’s layering
• Depth-First Search — used in Kuhn’s algorithm and Hopcroft-Karp’s augmentation
• Big-O Notation
• Micali-Vazirani — O(E√V) for general graphs; the natural next step after Hopcroft-Karp
• Edmonds’ Blossom Algorithm — the odd-cycle machinery that general matching needs
• Stable Matching — the adjacent, different problem: per-agent preferences and a no-blocking-pair constraint instead of a global count; read the callout under this note’s opening paragraph before assuming the two are related
• The Gale-Shapley Algorithm — deferred acceptance, the constructive existence proof for stable matchings
• Games and Strategic Systems in C MOC — where the preference-bearing side of “matching” lives
• SWE Interview Preparation MOC