Wolfram Demonstrations Project

The famous blossom algorithm due to Jack Edmonds (1965) finds a maximum matching in a graph. The problem is relatively easy in bipartite graphs through the use of augmenting paths, but the general case is more difficult. The algorithm starts with a maximal matching, which it tries to extend to a maximum matching. The key theorem is that a matching is maximum iff the matching does not admit an augmenting path. The blossom algorithm checks for the existence of an augmenting path by a tree search as in the bipartite case, but with special handling for the odd-length cycles that can arise in the general case. Such a cycle is called a blossom. The blossom can be shrunk and the search restarted recursively. If an augmenting path in a shrunken graph is ever found, it can be expanded up through the blossoms to yield an augmenting path in the original; that alternating path can be used to augment the matching by one edge. And if the recursive process runs into a state where there is no augmenting path, then there is none in the original graph. This Demonstration shows two cases of how blossom-shrinking leads to an augmentation of a maximal matching (red) to a maximum matching (blue).

Contributed by: Matthew Kusner and Stan Wagon
(Macalester College)

A matching in a graph is a collection of edges whose ends are disjoint. A maximal matching is one that cannot be extended to a larger matching; it is easy to find one by adding edges until further addition is not possible. A maximum matching is a matching containing the largest number of edges among all matchings. An augmenting path for a matching

is a path with an odd number of edges,

such that

and

. The symmetric difference of

with

yields a matching having one more edge than

For the basics of the Hungarian algorithm in the bipartite case, see the Demonstration "The Hungarian Maximum Matching Algorithm". For details of the shrinking process see [1, 3, 4]. The first example is from the notes of Zwick [4]. The second example is interesting because the second blossom uses an edge that arose from the shrinking of the first blossom, but is not an edge in the original graph.

While a recursive approach might not be the most efficient, it does work well for graphs of several thousand vertices. A more efficient implementation of the blossom algorithm that also includes the more difficult case of weighted edges can be found in [2].

References

[1] W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver, Combinatorial Optimization, New York: Wiley, 1998.

[2] V. Kolmogorov, "Blossom V: A New Implementation of a Minimum Cost Perfect Matching Algorithm," Mathematical Programming Computation 1(1), 2009 pp. 43–67.

[3] R. Tarjan, "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching," Course Notes, Department of Computer Science, Princeton University, 2002. http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf.

[4] U. Zwick, "Lecture Notes on: Maximum Matching in Bipartite and Non-Bipartite Graphs," 2009. http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf.