Matching and Flows

Matching theory studies how to pair elements optimally. It connects combinatorics, linear programming, and algorithm design.

Matching Basics

A matching M in a graph G = (V, E) is a set of pairwise non-adjacent edges — no two edges in M share a vertex.

A vertex is matched if it is an endpoint of some edge in M; otherwise it is unmatched (or free).

A maximum matching has the largest possible number of edges.

A perfect matching matches every vertex (|M| = |V|/2). Only possible if |V| is even.

A maximal matching cannot be extended by adding another edge (but may not be maximum).

Bipartite Matching

In a bipartite graph G = (U ∪ V, E), a matching pairs vertices from U with vertices from V.

Augmenting Paths

An augmenting path (relative to matching M) is a path that:

Starts at an unmatched vertex in U.
Alternates between unmatched and matched edges.
Ends at an unmatched vertex in V.

Berge's Theorem: A matching M is maximum iff there is no augmenting path.

Algorithm (Hungarian-style):

Start with an empty matching.
While an augmenting path exists:
- Find an augmenting path P.
- Augment: Flip matched/unmatched edges along P (M ⊕ P).
Return M.

Each augmentation increases |M| by 1.

Hopcroft-Karp Algorithm

Finds a maximum bipartite matching in O(E√V) time by finding multiple augmenting paths of the same shortest length simultaneously using BFS + DFS.

Hall's Theorem

Theorem (Hall's Marriage Theorem, 1935): A bipartite graph G = (U ∪ V, E) has a matching that saturates all of U iff for every subset S ⊆ U:

|N(S)| ≥ |S|

where N(S) is the set of neighbors of S in V.

In words: Every subset of U has enough neighbors in V.

Hall's condition is necessary and sufficient for a perfect matching from U to V.

Example: Can we assign n tasks to n workers, where each worker can do certain tasks?

Model as bipartite graph: workers on one side, tasks on the other. Edge if worker can do the task. Hall's condition checks feasibility.

Deficiency Version

If Hall's condition fails, the maximum matching size is:

|U| - max_{S ⊆ U} (|S| - |N(S)|)

The term max(|S| - |N(S)|) is the deficiency of the graph.

König's Theorem

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

ν(G) = τ(G)    (for bipartite G)

where ν = matching number, τ = vertex cover number.

A vertex cover is a set of vertices such that every edge has at least one endpoint in the set.

Note: This equality does NOT hold for general graphs. For example, in K₃ (triangle): ν = 1, τ = 2.

Relationship to LP Duality

König's theorem is a consequence of LP duality. The maximum matching LP and minimum vertex cover LP have the same optimal value for bipartite graphs (the LP relaxation has integer optimal solutions).

König-Egerváry in Weighted Setting

The Hungarian algorithm solves the assignment problem (minimum-weight perfect matching in bipartite graphs) in O(n³) time.

Stable Matching

The Stable Marriage Problem

Given n men and n women, each with a complete preference ranking of the other side, find a stable matching — a perfect matching with no blocking pair.

A blocking pair (m, w) exists if:

m prefers w to his current partner, AND
w prefers m to her current partner.

Gale-Shapley Algorithm (1962)

Initialize all men and women as free.
While there is a free man m:
    Let w = highest-ranked woman on m's list that m hasn't proposed to.
    If w is free:
        Match (m, w).
    Else if w prefers m to her current partner m':
        Match (m, w). Free m'.
    Else:
        w rejects m. (m remains free)

Properties:

Always terminates in at most n² proposals.
Always produces a stable matching.
The result is man-optimal (each man gets his best possible stable partner) and woman-pessimal.
Running the algorithm with women proposing gives the woman-optimal matching.
The set of stable matchings forms a distributive lattice.

Time: O(n²).

Applications: Medical residency matching (NRMP), school choice, kidney exchange.

Maximum Matching in General Graphs

For non-bipartite graphs, augmenting paths can encounter odd cycles (blossoms), which complicate the algorithm.

Edmonds' Blossom Algorithm (1965)

Finds maximum matching in general graphs in O(V²E) time.

Key idea: When an odd cycle (blossom) is found during augmenting path search, shrink the blossom to a single supernode and continue the search. After finding an augmenting path, expand blossoms to recover the actual path.

Improved: Micali-Vazirani algorithm achieves O(E√V) for general graphs.

Tutte's Theorem

A graph G has a perfect matching iff for every subset S ⊆ V:

o(G - S) ≤ |S|

where o(G - S) is the number of odd components in G - S.

This generalizes Hall's theorem to non-bipartite graphs.

Tutte-Berge Formula

The size of the maximum matching:

ν(G) = (|V| - max_{S ⊆ V}(o(G - S) - |S|)) / 2

Weighted Matching

Assignment Problem

Given a complete bipartite graph with edge weights, find the minimum (or maximum) weight perfect matching.

Hungarian Algorithm: O(n³).

Reduce rows and columns.
Find a maximum matching in the zero-weight subgraph.
If not perfect, adjust dual variables.
Repeat until perfect.

Residency matching: NRMP uses Gale-Shapley (Roth and Shapley won the 2012 Nobel Prize in Economics for this work).
School choice: Students are matched to schools based on preferences and priorities.
Kidney exchange: Patients and donors form a bipartite graph. Maximum matching maximizes transplants. Cycles and chains enable more complex exchanges.
Job assignment: Workers to tasks, maximizing productivity (assignment problem).
Network routing: Matching pairs of source-destination for non-interfering communication.
Compiler optimization: Register allocation uses matching concepts.
Online advertising: Ad slots matched to advertisers in real-time (online bipartite matching).
Ride-sharing: Matching riders to drivers.