# Chapter 60. Maximum Matching Algorithms

# Chapter 60. Maximum Matching Algorithms

A maximum matching algorithm finds a matching of largest possible size in a graph. Matching algorithms are among the most important combinatorial optimization methods. They appear in scheduling, assignment, routing, network design, computational biology, and resource allocation. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Matching_%28graph_theory%29?utm_source=chatgpt.com))

The structure of the graph strongly influences the complexity of the problem. Bipartite graphs admit especially elegant algorithms. General graphs require deeper structural ideas because odd cycles create additional complications.

This chapter develops the main algorithmic principles behind maximum matching.

## 60.1 The Maximum Matching Problem

Let

$$
G=(V,E)
$$

be a graph.

A matching is a set of pairwise disjoint edges. The goal is to find a matching of maximum size.

Formally, the problem asks for

$$
M \subseteq E
$$

such that:

1. No two edges in \(M\) share a vertex.
2. \(|M|\) is as large as possible.

The size of a maximum matching is denoted by

$$
\nu(G).
$$

The problem can be solved exactly in polynomial time.

## 60.2 Basic Strategy

Most matching algorithms follow the same general framework:

1. Start with an initial matching.
2. Search for an augmenting path.
3. Augment the matching along the path.
4. Repeat until no augmenting path exists.

The theoretical foundation is Berge's lemma.

## 60.3 Berge's Lemma

**Theorem 60.1. Berge's Lemma.**  
A matching \(M\) is maximum if and only if there exists no augmenting path with respect to \(M\). ([en.wikipedia.org](https://en.wikipedia.org/wiki/Berge%27s_lemma?utm_source=chatgpt.com))

An augmenting path is an alternating path whose endpoints are unmatched.

If such a path exists, flipping the matching status of its edges increases the matching size by one.

Suppose

$$
P=e_1,e_2,\ldots,e_{2k+1}
$$

alternates between nonmatching and matching edges, beginning and ending with nonmatching edges.

Then:

| Edge Type | Count |
|---|---|
| Nonmatching edges | \(k+1\) |
| Matching edges | \(k\) |

Flipping the path removes \(k\) edges and adds \(k+1\) edges.

Thus the matching size increases by one.

## 60.4 Augmentation

Let \(M\) be a matching and \(P\) an augmenting path.

Define the new matching:

$$
M' = M \triangle E(P),
$$

where

$$
\triangle
$$

denotes symmetric difference.

Thus:

| Edge in \(P\) | Action |
|---|---|
| In \(M\) | Remove |
| Not in \(M\) | Add |

The result is again a matching, and:

$$
|M'| = |M| + 1.
$$

This operation is called augmentation.

## 60.5 Naive Augmenting-Path Algorithm

The simplest maximum matching algorithm repeatedly searches for augmenting paths.

### Algorithm

1. Start with

$$
M=\varnothing.
$$

2. Search for an augmenting path.
3. If found, augment the matching.
4. Repeat until no augmenting path exists.

By Berge's lemma, the final matching is maximum.

### Complexity

Suppose augmenting paths are found using breadth-first search or depth-first search.

Each augmentation increases the matching size by one. Since the maximum size is at most

$$
\frac{|V|}{2},
$$

the number of augmentations is at most

$$
O(V).
$$

If each search costs

$$
O(E),
$$

then the total running time is

$$
O(VE).
$$

This is acceptable for small and moderate graphs but inefficient for very large instances.

## 60.6 Alternating Trees

Augmenting-path algorithms usually organize the search using alternating trees.

Start from an unmatched vertex.

Grow a tree whose edges alternate:

| Level | Edge Type |
|---|---|
| Even depth | Nonmatching edge |
| Odd depth | Matching edge |

This structure ensures that every root-to-vertex path is alternating.

If an unmatched vertex is reached at an even level, an augmenting path has been found.

Alternating trees are fundamental in both bipartite and general matching algorithms.

## 60.7 Bipartite Matching Algorithms

Bipartite graphs simplify the problem because they contain no odd cycles.

This allows augmenting paths to be found cleanly using layered searches.

### Layered Search

Let

$$
G=(X \cup Y,E)
$$

be bipartite.

Start from unmatched vertices in \(X\).

Construct layers:

| Step | Edge Type |
|---|---|
| From \(X\) to \(Y\) | Nonmatching edges |
| From \(Y\) to \(X\) | Matching edges |

This produces alternating paths automatically.

## 60.8 The Hopcroft-Karp Algorithm

The Hopcroft-Karp algorithm is the standard algorithm for maximum bipartite matching. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm?utm_source=chatgpt.com))

The key improvement is that the algorithm augments along many shortest augmenting paths simultaneously.

### Main Structure

Each phase contains:

1. Breadth-first search to compute distance layers.
2. Depth-first search to find vertex-disjoint shortest augmenting paths.
3. Simultaneous augmentation along all such paths.

This reduces the total number of phases dramatically.

### Complexity

The running time is

$$
O(E\sqrt{V}).
$$

This is one of the major results in combinatorial optimization.

## 60.9 Breadth-First Search Layers

During the Hopcroft-Karp algorithm, breadth-first search builds a layered graph.

Vertices are partitioned by distance from unmatched vertices.

The search respects alternation:

| Edge Traversed | Condition |
|---|---|
| Unmatched edge | Forward |
| Matching edge | Reverse |

The first layer containing unmatched vertices on the opposite side identifies shortest augmenting paths.

Only shortest augmenting paths are considered during the phase.

## 60.10 Why Shortest Paths Matter

Suppose one augments along arbitrary paths.

A later augmentation may destroy much of the previous structure.

The Hopcroft-Karp algorithm avoids this inefficiency.

By augmenting along many shortest disjoint paths simultaneously:

| Benefit | Result |
|---|---|
| Paths are vertex-disjoint | Augmentations do not interfere |
| Path lengths increase over time | Number of phases decreases |
| Many augmentations occur per phase | Faster convergence |

This leads to the

$$
O(E\sqrt{V})
$$

bound.

## 60.11 General Graph Matching

General graphs introduce new complications because odd cycles may appear.

In bipartite graphs, alternating trees never encounter parity conflicts. In arbitrary graphs, alternating paths may become trapped inside odd cycles.

These odd cycles are called blossoms.

Handling blossoms is the key difficulty in general matching algorithms.

## 60.12 Blossoms

A blossom is an odd cycle appearing during the search for augmenting paths.

Suppose an alternating tree reaches two vertices already connected by an edge. If the resulting cycle has odd length, the cycle may prevent straightforward augmentation.

For example:

$$
v_1v_2v_3v_4v_5v_1
$$

may form an alternating odd cycle.

The cycle obstructs the layered structure used in bipartite algorithms.

## 60.13 Edmonds' Blossom Algorithm

Edmonds introduced the blossom algorithm in 1965. It was the first polynomial-time algorithm for maximum matching in arbitrary graphs. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Blossom_algorithm?utm_source=chatgpt.com))

The main idea is blossom contraction.

### Blossom Contraction

Suppose an odd alternating cycle appears.

Contract the entire blossom into a single supervertex.

Then continue searching for augmenting paths in the contracted graph.

If an augmenting path is found, the contraction can later be expanded consistently.

This remarkable idea preserves correctness while eliminating odd-cycle obstructions.

## 60.14 Complexity of Blossom Algorithms

Early blossom algorithms had relatively high polynomial complexity.

Modern implementations achieve significantly better performance.

Typical bounds include:

| Algorithm | Complexity |
|---|---|
| Naive augmenting paths | \(O(VE)\) |
| Hopcroft-Karp | \(O(E\sqrt{V})\) |
| Edmonds blossom | Polynomial |
| Micali-Vazirani | \(O(E\sqrt{V})\) |

The Micali-Vazirani algorithm extends Hopcroft-Karp-type efficiency to general graphs.

## 60.15 Weighted Matching

In weighted matching problems, edges carry weights or costs.

The goal becomes:

| Objective | Optimization |
|---|---|
| Maximum-weight matching | Maximize total weight |
| Minimum-cost matching | Minimize total cost |

Weighted problems require more sophisticated methods.

## 60.16 The Hungarian Algorithm

The Hungarian algorithm solves weighted bipartite matching problems. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Hungarian_algorithm?utm_source=chatgpt.com))

The input is typically a cost matrix:

$$
C=(c_{ij}).
$$

The goal is to assign rows to columns with minimum total cost.

### Main Ideas

The algorithm maintains:

| Structure | Purpose |
|---|---|
| Dual variables | Maintain feasibility |
| Tight edges | Candidate assignments |
| Alternating trees | Search for augmenting structure |

The algorithm combines graph theory and linear programming duality.

### Complexity

Standard implementations run in polynomial time, commonly:

$$
O(n^3).
$$

## 60.17 Matching and Linear Programming

The maximum matching problem can be expressed as a linear program.

Introduce variables:

$$
x_e =
\begin{cases}
1, & e \in M, \\
0, & e \notin M.
\end{cases}
$$

The objective is:

$$
\max \sum_{e \in E} x_e.
$$

Subject to:

$$
\sum_{e \ni v} x_e \le 1
$$

for every vertex \(v\).

This formulation expresses the fact that each vertex participates in at most one matching edge.

In bipartite graphs, the linear relaxation automatically yields integral solutions. This property is one reason bipartite matching is especially tractable.

## 60.18 Matching Polytope

The set of all matchings forms a polytope in high-dimensional space.

Each matching corresponds to a \(0\)-\(1\) vector.

The convex hull of these vectors is called the matching polytope.

Edmonds characterized this polytope using linear inequalities, including blossom inequalities.

This result became foundational in polyhedral combinatorics.

## 60.19 Online Matching

In online matching problems, vertices or edges arrive over time.

The algorithm must make decisions immediately without knowing future inputs.

Applications include:

| Application | Online Interpretation |
|---|---|
| Advertisement allocation | Users arrive sequentially |
| Ride matching | Requests appear dynamically |
| Cloud scheduling | Jobs arrive continuously |

Online matching theory studies competitive algorithms and probabilistic guarantees.

## 60.20 Randomized Matching Algorithms

Randomization often improves matching algorithms.

Randomized algorithms appear in:

| Context | Purpose |
|---|---|
| Online matching | Adversarial robustness |
| Approximation algorithms | Faster computation |
| Large sparse graphs | Sampling techniques |
| Distributed systems | Conflict reduction |

One famous result is the Karp-Vazirani-Vazirani algorithm for online bipartite matching.

## 60.21 Parallel and Distributed Matching

Modern systems frequently require matching algorithms on massive graphs.

Parallel algorithms divide computation across processors.

Distributed algorithms allow vertices to make decisions locally.

Applications include:

| Domain | Graph Size |
|---|---|
| Social networks | Millions to billions of vertices |
| Web graphs | Massive scale |
| Communication networks | Dynamic topology |
| Data centers | Real-time allocation |

Efficient distributed matching remains an active research area.

## 60.22 Approximation Algorithms

For some matching variants, exact computation is expensive.

Approximation algorithms produce near-optimal solutions efficiently.

A simple greedy maximal matching gives a factor-\(2\) approximation to maximum matching.

More advanced approximation schemes achieve stronger guarantees for weighted and dynamic settings.

## 60.23 Applications

Maximum matching algorithms appear throughout science and engineering.

| Application | Matching Interpretation |
|---|---|
| Job assignment | Workers to tasks |
| Kidney exchange | Donors to recipients |
| Image processing | Feature correspondence |
| Scheduling | Tasks to machines |
| Resource allocation | Requests to servers |
| Transportation | Vehicles to routes |
| Chemistry | Molecular pairing |

The mathematical abstraction is extremely general.

## 60.24 Summary of Major Algorithms

| Algorithm | Graph Type | Complexity |
|---|---|---|
| Naive augmenting paths | General | \(O(VE)\) |
| Hopcroft-Karp | Bipartite | \(O(E\sqrt{V})\) |
| Blossom algorithm | General | Polynomial |
| Hungarian algorithm | Weighted bipartite | \(O(n^3)\) |
| Micali-Vazirani | General | \(O(E\sqrt{V})\) |

These algorithms form the foundation of practical matching computation.

## 60.25 Exercises

1. Prove Berge's lemma.

2. Show that augmenting along an augmenting path increases matching size by one.

3. Apply the naive augmenting-path algorithm to a small bipartite graph.

4. Explain why odd cycles create difficulties in general matching problems.

5. Describe blossom contraction in your own words.

6. Show that every maximal matching is at least half the size of a maximum matching.

7. Construct the flow network associated with a bipartite matching problem.

8. Explain why Hopcroft-Karp augments along shortest augmenting paths.

9. Write the linear programming formulation for maximum matching.

10. Explain why bipartite matching is easier than general matching.