47.04.04 · theoretical-cs / algorithms-analysis

Bipartite Matching: Hall's Theorem, Augmenting Paths, and the Hungarian Algorithm

shipped3 tiersLean: none

Anchor (Master): Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §26.3; Schrijver 2003 Combinatorial Optimization (Springer) §4.1-4.2 (the Hungarian method via linear programming duality, the primal-dual framework, extensions to general matching via Edmonds' blossom algorithm)

Intuition Beginner

Imagine a group of workers and a set of jobs. Each worker is qualified for some subset of the jobs. You want to assign workers to jobs so that no two workers get the same job and no worker gets more than one job. This is a bipartite matching problem.

The word "bipartite" means the graph has two sides (workers and jobs), and all edges go between the two sides — never within the same side. A "matching" is a set of edges where no two edges share a vertex — each worker gets at most one job, and each job gets at most one worker.

The central question is: what is the largest possible matching? How many workers can you simultaneously assign?

Hall's theorem gives a beautiful answer. It says: every worker can be matched to a distinct job if and only if for every subset of workers, the total number of jobs they are collectively qualified for is at least as large as the number of workers in the subset. This makes intuitive sense: if three workers are collectively qualified for only two jobs, you cannot match all three.

The augmenting-path algorithm finds a maximum matching by starting with any matching and repeatedly improving it. An augmenting path is a path that alternates between unmatched and matched edges, starting and ending at unmatched vertices. Flipping the edges along this path (matched becomes unmatched and vice versa) increases the matching size by one.

When no augmenting path exists, the matching is maximum. This is a consequence of the max-flow min-cut theorem applied to the flow network constructed from the bipartite graph.

The Hungarian algorithm solves the weighted version: each worker-job pair has a cost or value, and you want the matching with minimum total cost (or maximum value). It runs in $O (n^{3})$ time by maintaining a feasible "potential" function on the vertices and iteratively improving the matching.

Visual Beginner

A bipartite graph with a matching:

Workers (U)          Jobs (V)
  w1 ──────── j1
  w2 ──────── j2
  │  ╲           │
  │    ╲         │
  w3 ──────── j3
              /
            /
  w4 ──────── j4

The bold edges form a matching of size 3: $w 1 - j 1$ , $w 2 - j 2$ , $w 3 - j 3$ . Worker $w 4$ is unmatched.

An augmenting path: $w 4 \to j 3 \to w 3 \to j 4$ . This path has 3 edges, alternating unmatched (w4-j3), matched (w3-j3), unmatched (w3-j4). Flipping:

Before: M = {w1-j1, w2-j2, w3-j3}, size 3
After:  M' = {w1-j1, w2-j2, w3-j4, w4-j3}, size 4 (perfect!)

Concept	Definition	Condition
Matching	Set of disjoint edges	No shared vertices
Maximum matching	Largest possible	No augmenting path exists
Perfect matching	Covers all vertices	$
Hall's condition	$	N(S)

Worked example Beginner

Three students $s_{1}, s_{2}, s_{3}$ apply for three projects $p_{1}, p_{2}, p_{3}$ . The compatibility edges are: $s_{1}$ can do $p_{1}, p_{2}$ ; $s_{2}$ can do $p_{1}, p_{3}$ ; $s_{3}$ can do $p_{2}, p_{3}$ .

Start with an empty matching. Find an augmenting path from $s_{1}$ to $p_{1}$ : just the edge $(s_{1}, p_{1})$ . Add it. Matching: ${(s_{1}, p_{1})}$ , size 1.

Find an augmenting path from $s_{2}$ . $s_{2}$ is unmatched. Try $p_{1}$ : matched to $s_{1}$ . From $s_{1}$ , try $p_{2}$ : unmatched. Path: $s_{2} \to p_{1} \to s_{1} \to p_{2}$ . Flip: remove $(s_{1}, p_{1})$ , add $(s_{2}, p_{1})$ and $(s_{1}, p_{2})$ . Matching: ${(s_{2}, p_{1}), (s_{1}, p_{2})}$ , size 2.

Find an augmenting path from $s_{3}$ . $s_{3}$ is unmatched. Try $p_{2}$ : matched to $s_{1}$ . From $s_{1}$ , all neighbours ( $p_{1}, p_{2}$ ) are explored. $p_{1}$ is matched to $s_{2}$ . From $s_{2}$ , try $p_{3}$ : unmatched. Path: $s_{3} \to p_{2} \to s_{1} \to p_{1} \to s_{2} \to p_{3}$ . Flip: remove $(s_{1}, p_{2})$ and $(s_{2}, p_{1})$ , add $(s_{3}, p_{2})$ , $(s_{1}, p_{1})$ , and $(s_{2}, p_{3})$ . Matching: ${(s_{3}, p_{2}), (s_{1}, p_{1}), (s_{2}, p_{3})}$ , size 3. This is a perfect matching.

Check your understanding Beginner

Formal definition Intermediate+

Definition (bipartite matching). Let $G = (U \cup V, E)$ be a bipartite graph. A matching is a set $M \subseteq E$ such that no two edges in $M$ share a common endpoint. A maximum matching maximises $∣ M ∣$ . A perfect matching satisfies $∣ M ∣ = ∣ U ∣ = ∣ V ∣$ .

Theorem (Hall's marriage theorem). Let $G = (U, V, E)$ be a bipartite graph with $∣ U ∣ \leq ∣ V ∣$ . There exists a matching that covers every vertex in $U$ if and only if for every $S \subseteq U$ :

∣ N (S) ∣ \geq ∣ S ∣.

Proof. The forward direction is immediate: if a matching covers $U$ , then every $S \subseteq U$ is matched to distinct vertices in $V$ , so $∣ N (S) ∣ \geq ∣ S ∣$ .

For the backward direction, we prove the contrapositive. Suppose no matching covers $U$ . Let $M$ be a maximum matching, and let $u \in U$ be unmatched. Consider the set $Z$ of all vertices reachable from $u$ by alternating paths (paths alternating between edges not in $M$ and edges in $M$ ). Let $S = Z \cap U$ and $T = Z \cap V$ .

Every vertex in $T$ is matched (reached by a non-matching edge from $S$ and followed by a matching edge to $S$ ), so $∣ T ∣ = ∣ S ∣ - 1$ (one unmatched vertex $u$ is in $S$ ). Every neighbour of $S$ is in $T$ (otherwise there would be an augmenting path, contradicting maximality). So $N (S) = T$ and $∣ N (S) ∣ = ∣ T ∣ = ∣ S ∣ - 1 < ∣ S ∣$ . Hall's condition is violated. $□$

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

Proof. The max-flow reduction connects this to the max-flow min-cut theorem. Construct a flow network with source $s$ connected to $U$ (capacity 1), edges from $U$ to $V$ (capacity $\infty$ ), and $V$ connected to sink $t$ (capacity 1). The maximum flow equals the maximum matching. The minimum $s$ - $t$ cut corresponds to a vertex cover: the $U$ -side vertices in the cut plus the $V$ -side vertices in the cut form a vertex cover of the same size as the max flow. $□$

Counterexamples to common slips

"Hall's theorem applies to any graph." Hall's theorem specifically requires a bipartite graph. For general graphs, the Tutte-Berge formula replaces Hall's condition.
"The Hungarian algorithm finds maximum-cardinality matchings." The Hungarian algorithm finds maximum-weight matchings in weighted bipartite graphs. For unweighted maximum matching, the augmenting-path or Hopcroft-Karp algorithm is used.
"A maximum matching is the same as a maximal matching." A maximal matching cannot be extended by adding an edge. A maximum matching has the largest possible size. A maximal matching can be half the size of a maximum matching.

Key theorem with proof Intermediate+

Theorem (augmenting-path algorithm). A matching $M$ in a bipartite graph $G$ is maximum if and only if there is no $M$ -augmenting path.

Proof. If an $M$ -augmenting path $P$ exists, flipping edges along $P$ produces a matching of size $∣ M ∣ + 1$ , so $M$ is not maximum.

Conversely, suppose $M$ is not maximum. Let $M^{*}$ be a maximum matching with $∣ M^{*} ∣ > ∣ M ∣$ . Consider the symmetric difference $M \oplus M^{*} = (M ∖ M^{*}) \cup (M^{*} ∖ M)$ . Each vertex is incident to at most one edge from $M$ and at most one from $M^{*}$ , so every component of $M \oplus M^{*}$ is a path or an even cycle. Since $∣ M^{*} ∣ > ∣ M ∣$ , there must be a component that is a path starting and ending with $M^{*}$ -edges. This path starts and ends at $M$ -unmatched vertices and alternates between $M^{*}$ -edges (not in $M$ ) and $M$ -edges (in $M$ ). This is an $M$ -augmenting path. $□$

Theorem (Hungarian algorithm complexity). The Hungarian algorithm finds a maximum-weight perfect matching in a complete bipartite graph $K_{n, n}$ with edge weights $w_{ij}$ in $O (n^{3})$ time.

Proof sketch. The algorithm maintains a feasible potential $(u, v)$ where $u_{i}$ for $i \in U$ and $v_{j}$ for $j \in V$ satisfy $u_{i} + v_{j} \geq w_{ij}$ for all $i, j$ . The equality subgraph $G_{=}$ has edge $(i, j)$ iff $u_{i} + v_{j} = w_{ij}$ . The algorithm iteratively:

Finds a maximum matching in $G_{=}$ (using the augmenting-path method).
If the matching is perfect, it is optimal by LP duality.
If not, updates the potential to add edges to $G_{=}$ (tightening the dual) and repeats.

Each potential update increases the size of the matching or adds edges, and the total number of iterations is $O (n)$ , each taking $O (n^{2})$ time. Total: $O (n^{3})$ . $□$

Bridge. The augmenting-path method for bipartite matching builds toward the entire theory of combinatorial optimisation as the interplay between primal solutions (matchings) and dual certificates (vertex covers, potentials): the central insight is that Hall's condition provides the structural reason a matching exists, and this is exactly what makes bipartite matching the model problem for the max-flow min-cut framework. This appears again in 47.04.03 where the Ford-Fulkerson algorithm generalises augmenting paths from matchings to arbitrary flows, and in 47.04.06 where minimum spanning trees use a dual cut-based optimality condition analogous to König's theorem. The foundational reason bipartite matching is tractable is that the bipartite structure prevents the "blossom" obstructions that Edmonds' general matching algorithm must handle. Putting these together with the Hungarian algorithm shows that the primal-dual framework — simultaneously maintaining a feasible matching and a feasible potential — is the generalises from the specific bipartite setting to all of linear programming.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Let $G$ be a bipartite graph with parts $U = {u_{1}, u_{2}, u_{3}, u_{4}}$ and $V = {v_{1}, v_{2}, v_{3}, v_{4}}$ where $u_{i}$ is adjacent to $v_{j}$ iff $i \neq = j$ . Find a maximum matching and a minimum vertex cover, verifying König's theorem.

Answer

A perfect matching: $M = {(u_{1}, v_{2}), (u_{2}, v_{3}), (u_{3}, v_{4}), (u_{4}, v_{1})}$ . Size 4. A minimum vertex cover: any set of 4 vertices that hits all edges. But since every $u_{i}$ is connected to 3 $v_{j}$ s, and there are $4 \times 3 = 12$ edges, a vertex cover of size 3 would need to cover all 12 edges, but each vertex covers at most 4 edges (a $v_{j}$ covers $3$ edges from $u_{i}$ with $i \neq = j$ , plus... actually each $v_{j}$ covers exactly 3 edges). So a cover of size 3 covers at most 9 edges, which is less than 12. A cover of size 4: ${v_{1}, v_{2}, v_{3}, v_{4}}$ covers all 12 edges. So the minimum vertex cover has size 4, matching the maximum matching size.

Exercise 5 (medium, symbolic).

Run the Hungarian algorithm on the following $3 \times 3$ cost matrix and find the minimum-cost assignment:

C = 123246369

Answer

Step 1: Subtract row minima. Row 1: subtract 1. Row 2: subtract 2. Row 3: subtract 3.

C^{'} = 000123246

Step 2: Subtract column minima. Column 1: 0. Column 2: 1. Column 3: 2.

C^{''} = 000012024

Step 3: Find maximum matching of zero-entries. Row 1 can match to columns 1, 2, or 3 (all zero). Row 2 matches to column 1 (zero). Row 3 matches to column 1 (zero). Only one row can take column 1. Matching: row 1 $\to$ column 2, row 2 $\to$ column 1, row 3 $\to$ column 3 (cost $2 + 2 + 6 = 10$ ). Or: row 1 $\to$ column 3, row 2 $\to$ column 1, row 3 $\to$ column 2 (cost $3 + 2 + 6 = 11$ ). Optimal: row 1 $\to$ column 1, row 2 $\to$ column 2, row 3 $\to$ column 3, total cost $= 1 + 4 + 9 = 14$ . But checking zero-entries: row 1 can go to col 1 (zero after column reduction? col 1 min is 0, already subtracted). Actually all entries in row 1 are 0 after step 2. Let me reconsider: the zero-covering gives the assignment. Minimum cost = $1 + 4 + 9 = 14$ , but row 1 $\to$ col 3, row 2 $\to$ col 1, row 3 $\to$ col 2 gives $3 + 2 + 6 = 11$ . And row 1 $\to$ col 2, row 2 $\to$ col 1, row 3 $\to$ col 3 gives $2 + 2 + 9 = 13$ . The minimum is 11: $(1, 3), (2, 1), (3, 2)$ .

Exercise 6 (hard, symbolic).

Prove that the Hopcroft-Karp algorithm finds a maximum bipartite matching in $O (∣ E ∣ ∣ V ∣)$ time.

Hint

The algorithm finds a maximal set of vertex-disjoint shortest augmenting paths in each phase, doubling the shortest path length every $O (∣ V ∣)$ phases.

Answer

The Hopcroft-Karp algorithm works in phases. In each phase, it uses BFS to find the length $k$ of the shortest augmenting path, then uses DFS to find a maximal set of vertex-disjoint augmenting paths of length $k$ . Each phase takes $O (∣ E ∣)$ time.

After $∣ V ∣$ phases, the shortest augmenting path has length $> ∣ V ∣$ . This means there are fewer than $∣ V ∣$ unmatched vertices reachable by alternating paths. Since each augmenting path increases the matching by 1, at most $∣ V ∣$ more phases are needed. Total phases: $O (∣ V ∣)$ . Total time: $O (∣ E ∣ ∣ V ∣)$ .

More precisely: let $M_{k}$ be the matching after $k$ phases and $d_{k}$ the shortest augmenting path length. The maximal set of disjoint paths in each phase ensures $d_{k + 1} \geq d_{k}$ . After $∣ V ∣$ phases, $d_{k} > 2 ∣ V ∣$ , which means the matching is within $∣ V ∣$ of optimal (by the Berge theorem and the fact that long augmenting paths require many unmatched vertices). So at most $∣ V ∣$ additional phases suffice.

Exercise 7 (hard, symbolic).

Prove König's theorem: in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Answer

Let $M$ be a maximum matching. Construct a minimum vertex cover as follows. Let $U_{L}$ be the set of unmatched vertices in $U$ . Let $Z$ be the set of all vertices reachable from $U_{L}$ by alternating paths (using unmatched edges from $U$ to $V$ and matched edges from $V$ to $U$ ). Define the vertex cover $C = (U ∖ Z) \cup (V \cap Z)$ .

$C$ is a vertex cover: every edge $(u, v)$ with $u \in U, v \in V$ is covered. If $u \in Z$ and $v \in / Z$ , then $(u, v)$ is a matched edge (otherwise $v$ would be added to $Z$ ), so $v \in V ∖ Z$ . But then $(u, v)$ is matched with $u \in Z \cap U$ and $v \in / Z$ . Since $u$ is reachable by an alternating path, the matched edge from $u$ goes to $v$ (which is not in $Z$ ). But alternating paths use matched edges from $V$ to $U$ , so $v$ should be in $Z$ . Contradiction. If $u \in / Z$ and $v \in Z$ : covered since $v \in V \cap Z \subseteq C$ . If both in $Z$ or both not in $Z$ : covered.

$∣ C ∣ = ∣ M ∣$ : $U ∖ Z$ consists of matched vertices not reachable by alternating paths. $V \cap Z$ consists of matched vertices reachable by alternating paths. The mapping from $C$ to $M$ is a bijection.

Since any vertex cover has size $\geq ∣ M ∣$ (each edge of $M$ needs a distinct cover vertex), $C$ is a minimum vertex cover with $∣ C ∣ = ∣ M ∣$ .

Exercise 8 (hard, symbolic).

A Latin rectangle is an $r \times n$ matrix with entries from ${1, \dots, n}$ such that no symbol repeats in any row or column. Use Hall's theorem to prove that any $r \times n$ Latin rectangle with $r < n$ can be extended to an $(r + 1) \times n$ Latin rectangle.

Answer

Define a bipartite graph where $U$ is the set of $n$ columns and $V$ is the set of symbols ${1, \dots, n}$ . Place an edge $(j, s)$ if symbol $s$ does not appear in column $j$ of the existing rectangle. Each column has exactly $n - r$ unused symbols (since $r$ symbols are already used in that column). Each symbol $s$ appears exactly once in each row, so exactly $r$ times total, hence is unused in exactly $n - r$ columns.

For any subset $S \subseteq U$ of columns, the total number of edges from $S$ to $N (S)$ is $∣ S ∣ (n - r)$ (each column has $n - r$ edges). Each symbol in $N (S)$ has at most $n - r$ edges. So $∣ S ∣ (n - r) \leq ∣ N (S) ∣ (n - r)$ , giving $∣ N (S) ∣ \geq ∣ S ∣$ . Hall's condition holds, so a perfect matching exists. This matching assigns to each column a distinct unused symbol, forming a new row. The result is an $(r + 1) \times n$ Latin rectangle.

Lean formalization Intermediate+

Mathlib has Combinatorics.SimpleGraph.Matching and Combinatorics.Hall with a proof of Hall's marriage theorem. The augmenting-path algorithm, König's theorem, and the Hungarian algorithm are not formalised. The foundational gap is the absence of a verified maximum-matching algorithm (either augmenting-path or Hopcroft-Karp) with a correctness proof, and the Hungarian algorithm for weighted matching. König's theorem connecting matchings to vertex covers in bipartite graphs would be a natural target for formalisation. This unit ships without a lean_module.

Advanced results Master

Three directions extend bipartite matching theory.

Theorem 1 (Edmonds' blossom algorithm). Maximum matching in general (non-bipartite) graphs can be found in $O (∣ V ∣^{2} ∣ E ∣)$ time. The algorithm handles "blossoms" — odd cycles that arise in non-bipartite graphs and prevent the simple augmenting-path approach from working ^{[CLRS §26.3]}.

In bipartite graphs, alternating paths never cycle back to a previously visited vertex on the same side. In general graphs, odd cycles ("blossoms") can trap the search. Edmonds' algorithm contracts blossoms into single vertices, finds augmenting paths in the contracted graph, and then expands the blossoms to recover the augmenting path in the original graph.

Theorem 2 (LP relaxation integrality). The natural linear programming relaxation of bipartite matching (maximise $\sum_{e} x_{e}$ subject to $\sum_{e ∋ v} x_{e} \leq 1$ for all $v$ , $x_{e} \geq 0$ ) has an integral optimum. This is dual to the LP relaxation of vertex cover, and both are integral for bipartite graphs.

This integrality is the foundational reason bipartite matching can be solved in polynomial time via linear programming. The Hungarian algorithm is essentially a primal-dual method for this LP pair.

Theorem 3 (online bipartite matching). In the online setting where vertices on one side arrive one at a time and must be matched immediately or never, the optimal competitive ratio is $1 - 1/ e \approx 0.632$ (Karp, Vazirani, and Vazirani 1990). The RANKING algorithm achieves this ratio.

Online matching has applications in ad allocation, job scheduling, and kidney exchange. The competitive ratio of $1 - 1/ e$ matches the performance of the greedy algorithm for the secretary problem.

Synthesis. Bipartite matching is the foundational reason that the max-flow framework provides a unified theory of combinatorial optimisation: the central insight is that the reduction from matching to max-flow, combined with LP duality and Hall's theorem, creates a three-way equivalence between combinatorial, algebraic, and optimisation perspectives on the same problem. This builds toward the general matching theory of Edmonds' blossom algorithm in 47.04.06 where the bipartite restriction is removed, and appears again in 47.02.03 where the contrast between tractable matching and NP-complete Hamiltonian cycle illustrates the boundary of polynomial-time computation. The generalises from the specific augmenting-path method to the entire primal-dual framework, and putting these together with König's theorem shows that the matching-cover duality is the structural backbone of bipartite graph theory.

Full proof set Master

Proposition 1 (Hall's theorem). A bipartite graph $G = (U, V, E)$ has a matching covering $U$ iff $∣ N (S) ∣ \geq ∣ S ∣$ for all $S \subseteq U$ .

Proof. Forward: if matching $M$ covers $U$ , every $S \subseteq U$ is matched to $∣ S ∣$ distinct vertices in $V$ , all in $N (S)$ , so $∣ N (S) ∣ \geq ∣ S ∣$ .

Backward (contrapositive): suppose no matching covers $U$ . Let $M$ be a maximum matching and $u_{0} \in U$ unmatched. Build $Z$ = vertices reachable from $u_{0}$ via alternating paths. Set $S = Z \cap U$ , $T = Z \cap V$ . Every $v \in T$ is reached from some $u \in S$ via a non-matching edge, then followed by a matching edge back to $S$ (since $M$ is maximum, no alternating path reaches an unmatched vertex in $V$ ). So $M$ gives a bijection from $T$ to $S ∖ {u_{0}}$ , giving $∣ T ∣ = ∣ S ∣ - 1$ . Every neighbour of $S$ is in $T$ (otherwise there is an augmenting path). So $∣ N (S) ∣ = ∣ T ∣ = ∣ S ∣ - 1 < ∣ S ∣$ . $□$

Proposition 2 (König's theorem). In a bipartite graph, the maximum matching size equals the minimum vertex cover size.

Proof. Let $M$ be a maximum matching. Construct $Z$ from unmatched $U$ -vertices via alternating paths. The vertex cover is $C = (U ∖ Z) \cup (V \cap Z)$ .

Cover: every edge $(u, v)$ with $u \in U, v \in V$ is covered. If $u \in Z \cap U$ and $v \in / Z$ : the edge $(u, v)$ is in $M$ (otherwise $v$ would be in $Z$ ). But matched edges go from $Z \cap U$ to $Z \cap V$ , so $v \in Z$ . Contradiction. So either $u \in / Z$ (in $C$ ) or $v \in Z$ (in $C$ ).

Size: the matching $M$ pairs $U ∖ Z$ with $V ∖ Z$ and $U \cap Z$ with $V \cap Z$ (by the alternating-path structure). So $∣ M ∣ = ∣ U ∖ Z ∣ + ∣ V \cap Z ∣ = ∣ C ∣$ . Since any vertex cover has size $\geq ∣ M ∣$ , $C$ is minimum. $□$

Connections Master

47.04.03 — The max-flow min-cut theorem underpins the matching-to-flow reduction; Ford-Fulkerson augmenting paths generalise matching augmenting paths.
40.04.01 — Basic graph definitions (bipartite, adjacency, degree) provide the foundation on which matching theory is built.
47.02.03 — Bipartite matching is in P while Hamiltonian cycle is NP-complete; the contrast illustrates the tractability boundary for graph problems.
47.04.06 — Minimum spanning trees and maximum matchings are both fundamental P-time graph optimisation problems with elegant structural characterisations.
47.03.03 — The LP integrality of bipartite matching connects to circuit complexity through the theory of totally unimodular matrices.

Historical & philosophical context Master

Hall's theorem was proved by Philip Hall in 1935, though equivalent results were known to König (1916) and Menger (1927) in related forms. Hall's formulation in terms of the marriage problem (matching men to women subject to compatibility constraints) gave the theorem its popular name and直观 appeal.

The Hungarian algorithm was published by Harold Kuhn in 1955, who attributed the underlying ideas to the work of Hungarian mathematicians König and Egerváry. Kuhn showed that the primal-dual method for the assignment problem runs in $O (n^{3})$ time. James Munkres (1957) proved that Kuhn's algorithm always terminates in $O (n^{3})$ steps, and the algorithm is often called the Kuhn-Munkres algorithm.

König's theorem (1916) was one of the earliest results connecting matchings to vertex covers, establishing the minimax relationship that later generalised to the max-flow min-cut theorem. The equivalence between maximum matching and minimum vertex cover in bipartite graphs was a precursor to LP duality theory ^{[CLRS §26.3]}.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@article{hall1935representatives,
  author  = {Hall, Philip},
  title   = {On Representatives of Subsets},
  journal = {Journal of the London Mathematical Society},
  volume  = {10},
  number  = {1},
  pages   = {26--30},
  year    = {1935},
}
@article{kuhn1955hungarian,
  author  = {Kuhn, Harold W.},
  title   = {The Hungarian Method for the Assignment Problem},
  journal = {Naval Research Logistics Quarterly},
  volume  = {2},
  pages   = {83--97},
  year    = {1955},
}
@book{schrijver2003combinatorial,
  author    = {Schrijver, Alexander},
  title     = {Combinatorial Optimization: Polyhedra and Efficiency},
  publisher = {Springer},
  year      = {2003},
}

Prerequisites

47.04.03
40.04.01

Tier anchors

beginner: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §26.3 (maximum bipartite matching via max-flow, augmenting paths, the concept of matching workers to jobs)
intermediate: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §26.3 (Hall's theorem, the augmenting-path algorithm, König's theorem, the Hungarian algorithm for weighted bipartite matching)
master: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §26.3; Schrijver 2003 Combinatorial Optimization (Springer) §4.1-4.2 (the Hungarian method via linear programming duality, the primal-dual framework, extensions to general matching via Edmonds' blossom algorithm)

References

Cormen, T. H., Leiserson, R. L., Rivest, C. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Section 26.3 defines a matching in a bipartite graph $G = (U \cup V, E)$ as a set $M \subseteq E$ of pairwise vertex-disjoint edges; a maximum matching is one of maximum cardinality; a perfect matching covers all vertices. Hall's theorem states that a bipartite graph with parts $U$ and $V$ where $∣ U ∣ \leq ∣ V ∣$ has a matching that covers $U$ iff for every $S \subseteq U$ , $∣ N (S) ∣ \geq ∣ S ∣$ , where $N (S)$ is the set of neighbours of $S$ . The augmenting-path algorithm (based on Ford-Fulkerson) finds a maximum bipartite matching in $O (∣ V ∣ \cdot ∣ E ∣)$ time by reducing to max-flow: add a source $s$ connected to all $U$ -vertices, a sink $t$ connected to all $V$ -vertices, direct all edges from $U$ to $V$ , and set all capacities to 1; a maximum flow gives a maximum matching. König's theorem states that the size of a maximum matching equals the size of a minimum vertex cover in bipartite graphs. The Hungarian algorithm solves the assignment problem (maximum-weight bipartite matching) in $O (n^{3})$ time using the primal-dual method.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m