Micali-Vazirani Algorithm

Purpose: Find a maximum cardinality matching in a general (non-bipartite) graph in $O(m\sqrt{n})$ — matching the bipartite bound of Hopcroft-Karp. The fastest known algorithm for general matching (1980).

The framework

Like Hopcroft-Karp, it works in phases, each finding a maximal set of vertex-disjoint shortest augmenting paths:

1. After $\sqrt{n}$ phases, every remaining augmenting path has length $>\sqrt{n}$.
2. At most $\sqrt{n}$ such paths can be vertex-disjoint.
3. So $O(\sqrt{n})$ phases suffice in total. Each phase must run in $O(m)$.

For bipartite graphs a simple BFS/DFS achieves the $O(m)$ phase. For general graphs, odd cycles (blossoms) break the layering, and handling them in linear time per phase is the entire difficulty.

The hard part: blossoms in linear time

Edmonds’ blossom algorithm contracts an odd cycle whenever it finds one, at $O(n)$ cost per contraction — fine for one augmenting path, far too slow for a whole phase.

Micali and Vazirani replace contraction with a delicate bookkeeping of two distances per vertex:

• evenlevel[v] — length of the shortest even-length alternating path from a free vertex to $v$;
• oddlevel[v] — the same for odd length.

A vertex may be reachable at both parities, and the interplay of these two levels is what encodes blossom structure without explicitly contracting anything. Blossoms are detected as bridges — edges whose endpoints’ levels are inconsistent with a simple layering — and are processed by a “double depth-first search” that finds two disjoint paths through the blossom simultaneously.

Complexity

• Time: $O(m\sqrt{n})$
• Space: $O(n+m)$
• Reputation: one of the hardest correct algorithms to implement. The original paper’s proof was incomplete; a full correctness proof took until 1994 (Vazirani), and few correct implementations exist.

Matching algorithms in practice

Graph	Algorithm	Time
Bipartite, small	Kuhn	$O(nm)$
Bipartite	Hopcroft-Karp or Dinic	$O(m\sqrt{n})$
Bipartite, weighted	Hungarian	$O(n^3)$
General	Blossom	$O(n^3)$ or $O(nm\alpha )$
General	Micali-Vazirani	$O(m\sqrt{n})$
General, weighted	Blossom V (Kolmogorov)	$O(n^3)$ practical
Existence of perfect matching only	Tutte matrix + random determinant	$O(n^{\omega })$ randomized

What to write

For general matching, use a randomised Blossom implementation ($O(n^3)$) — it handles $n\le 500$ comfortably, which covers essentially every contest problem. If you only need to decide whether a perfect matching exists, the Tutte matrix trick (fill a skew-symmetric matrix with random values and test whether its determinant is nonzero) is 15 lines and $O(n^3)$.

Variants / Use Cases

• General Matching — the topic page
• Blossom algorithm — the implementable general matcher
• Hopcroft-Karp — the bipartite version of the same phase structure
• Tutte-Berge formula — the max-matching analogue of König’s theorem for general graphs