9873

The Blossom Algorithm for Maximum Matching

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).

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+