Bipartite Matching¶

From Computability, Complexity & Algorithms — Charles Brubaker and Lance Fortnow

Bipartite Graphs¶

A graph \(G = (L, R, E)\) is bipartite if its vertices can be partitioned into two disjoint sets \(L\) (left) and \(R\) (right) such that every edge has one endpoint in \(L\) and one in \(R\).

BipartiteExample — Example bipartite graph — green vertices in \(L\), orange vertices in \(R\).¶

Equivalent characterization: A graph is bipartite if and only if it contains no odd-length cycles, which is equivalent to being 2-colorable.

OddCycleExample — Adding an edge that creates an odd-length cycle makes the graph non-bipartite.¶

DeleteEdgesQuiz — *Quiz:* Which edges must be removed to make a non-bipartite graph bipartite?¶

Matching¶

A matching \(M\) is a subset of edges where no two edges share a vertex.

Two important distinctions:

Maximal matching — no additional edge can be added while preserving the matching property (locally optimal, but not necessarily globally optimal).
Maximum matching — matching with the largest possible cardinality (globally optimal).

A maximal matching is not necessarily a maximum matching.

MaximumMatchingDef — A maximum matching can have greater cardinality than some maximal matchings.¶

Real-World Applications¶

Bipartite matching models many assignment problems:

Compatible roommate pairings
Taxi-to-customer assignment (minimizing pickup time)
Professor-to-class scheduling
Organ donor-to-patient matching

MatchingApplicationsQuiz — *Quiz:* Identify which real-world scenarios reduce to maximum matching.¶

Reduction to Maximum Flow¶

Maximum bipartite matching reduces to maximum flow by constructing a flow network:

Add a source \(s\) connected to every vertex in \(L\) (capacity 1).
Add a sink \(t\) connected from every vertex in \(R\) (capacity 1).
Direct all original edges \(L \to R\) (capacity 1).
Run Ford-Fulkerson on the resulting network.

Each unit of flow corresponds to one matched edge.

FlowNetworkDef — Flow network construction from bipartite graph with unit capacities.¶

Time complexity: \(O(EV)\) — the total flow is at most \(|V|\), and each augmenting path costs \(O(E)\) via BFS.

FlowNetworkReductionRunningTime — Time complexity analysis of the Ford-Fulkerson reduction.¶

Augmenting Paths in Bipartite Graphs¶

In the residual flow network, augmenting paths correspond directly to alternating paths in the original bipartite graph.

AugPathsInResFlowNetwork — Residual network showing augmenting paths in the maximum flow context.¶

AugPathsInResBipartite — Special properties of augmenting paths in bipartite residual networks.¶

An alternating path has edges alternately inside \(M\) and outside \(M\). An augmenting path is an alternating path whose first and last vertices are both unmatched.

AugPathInBipartite — An augmenting path (blue) in a bipartite graph, with matching edges in purple.¶

Augmenting path algorithm:

\[M \leftarrow \emptyset\]

\[\textbf{while } \exists \text{ augmenting path } p: \quad M \leftarrow M \oplus p\]

where the symmetric difference is defined as:

\[M \oplus p = (M \cup p) \setminus (M \cap p)\]

Applying \(M \oplus p\) flips matched/unmatched edges along \(p\), increasing \(|M|\) by exactly 1.

Vertex Cover and König’s Theorem¶

A vertex cover is a set \(S \subseteq V\) such that every edge has at least one endpoint in \(S\).

VertexCoverStep1 — A single vertex (orange) covering three edges.¶

VertexCoverBig — A vertex cover that covers all edges in the graph.¶

MinVertexCoverQuiz — *Quiz:* Find the minimum vertex cover of a given graph.¶

Key observation: \(|M| \leq |S|\) for any matching \(M\) and vertex cover \(S\), because each matched edge needs at least one vertex in \(S\).

MaxMatchingMinVertexCoverThrm — **König’s Theorem:** In any bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover.¶

\[\max |M| = \min |S|\]

Proof Sketch¶

Define the set \(H\) as all vertices reachable via alternating paths from unmatched \(L\)-vertices.

DefOfSetH — Set \(H\) — vertices reachable via alternating paths from unmatched vertices in \(L\).¶

HComplement — Full partition showing \(H\) and its complement in the graph.¶

Construct the vertex cover as \((L \setminus H) \cup (R \cap H)\):

VertexCoverConstruction — Minimum vertex cover constructed from the partition of \(H\) and its complement.¶

This cover has size equal to the maximum matching, proving König’s theorem.

Hall’s Marriage Theorem¶

The neighborhood \(N(X)\) of a set \(X \subseteq L\) is the set of all vertices in \(R\) adjacent to at least one vertex in \(X\).

NeighborhoodDef — Neighborhood \(N(X)\) — green vertices adjacent to orange subset \(X\).¶

NoHopeForPM — When Hall’s condition fails, no perfect matching can exist.¶

Hall’s Theorem (Frobenius-Hall):

A matching of size \(|L|\) exists if and only if:

\[\forall\, X \subseteq L,\quad |N(X)| \geq |X|\]

A perfect matching satisfies \(|M| = |L| = |R|\), matching every vertex on both sides.

Forward direction (\(\Rightarrow\)):: If a matching of size \(|L|\) exists, then for any \(X \subseteq L\) the matched partners form a set \(Y \subseteq N(X)\) with \(|Y| = |X|\), so \(|N(X)| \geq |X|\).

HallForward — Matched vertices \(Y \subseteq N(X)\) certify \(|N(X)| \geq |X|\) in the forward direction.¶

Backward direction (\(\Leftarrow\)):: By contrapositive — if no matching of size \(|L|\) exists, use set \(H\) to find \(X\) with \(|N(X)| < |X|\).

HallBackward — Set \(H\) construction for the backward direction of Hall’s theorem proof.¶

PMQuiz — *Quiz:* Which conditions guarantee a perfect matching?¶

Hopcroft-Karp Algorithm¶

Hopcroft-Karp improves on the basic augmenting-path approach by finding multiple augmenting paths simultaneously per phase.

Time complexity: \(O(E\sqrt{V})\)

HopcroftKarpAlg — Pseudocode for the Hopcroft-Karp algorithm.¶

HopcroftKarpThrm — Theorem stating the \(O(E\sqrt{V})\) time complexity of Hopcroft-Karp.¶

Algorithm (each phase):

BFS from all unmatched \(L\)-vertices to build an alternating level graph.
Find a maximal set of vertex-disjoint shortest augmenting paths via DFS.
Augment \(M\) along all found paths simultaneously: \(M \leftarrow M \oplus \text{paths}\).
Delete traversed vertices and orphaned edges; repeat.

LevelGraph — Original graph (left) and its alternating level graph built by BFS (right).¶

Key Lemmas¶

Matching differences lemma: If \(M^*\) is a maximum matching and \(M\) is any matching, then \(M^* \oplus M\) contains exactly \(|M^*| - |M|\) vertex-disjoint augmenting paths.

Shortest augmenting path lemma: Augmenting along shortest augmenting paths never decreases the length of the shortest remaining augmenting path.

ShortestAugmentingPathCorollary — Corollary to the shortest augmenting path lemma.¶

Phase count lemma: Each phase increases the length of the shortest augmenting path by at least 2, so the number of phases is \(O(\sqrt{V})\).

NumberOfPhasesDiagram — Distribution of augmenting path lengths across phases.¶

NumberOfPhasesProof — Proof summary: \(O(\sqrt{V})\) phases, each taking \(O(E)\) → total \(O(E\sqrt{V})\).¶

After \(\lceil\sqrt{V}\rceil\) phases the shortest augmenting path has length \(\geq 2\lceil\sqrt{V}\rceil + 1\), and the remaining matching deficit is \(\leq \lceil\sqrt{V}\rceil\), so at most \(\lceil\sqrt{V}\rceil\) additional single-path augmentations suffice.

Complexity Summary¶

Algorithm	Time Complexity
Ford-Fulkerson reduction	\(O(EV)\)
Hopcroft-Karp	\(O(E\sqrt{V})\)

Key Formulas¶

\[G = (L, R, E), \quad \text{every edge between } L \text{ and } R\]

\[M \oplus p = (M \cup p) \setminus (M \cap p) \quad \text{(symmetric difference)}\]

\[\forall\, X \subseteq L,\quad |N(X)| \geq |X| \quad \text{(Hall's condition)}\]

\[|M| = |L| = |R| \quad \text{(perfect matching)}\]

\[\max|M| = \min|S| \quad \text{(König's theorem, bipartite graphs only)}\]

\[O(\sqrt{V}) \text{ phases} \times O(E) \text{ per phase} = O(E\sqrt{V}) \quad \text{(Hopcroft-Karp)}\]