Blossom Algorithm

The blossom algorithm (Edmonds 1965) finds a maximum independent edge set in a (possibly weighted) graph. While a maximum independent edge set can be found fairly easily for a bipartite graph using the Hungarian maximum matching algorithm, the general case is more difficult. Edmonds's blossom algorithm starts with a maximal independent edge set, which it tries to extend to a maximum independent edge set using the property 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.

REFERENCES

Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial Optimization. New York: Wiley, 1998.

Edmonds, J. "Paths, Trees, and Flowers." Canad. J. Math. 17, 449-467, 1965.

Gabow, H N. and Tarjan, R E. "Faster Scaling Algorithms for General Graph Matching Problems." J. ACM 38, 815-853, 1991.

Kolmogorov, V. "Blossom V: A New Implementation of a Minimum Cost Perfect Matching Algorithm." Mathematical Programming Comput. 1, 43-67, 2009.

 Kusner, M. and Wagon, S. "The Blossom Algorithm for Maximum Matching." http://demonstrations.wolfram.com/TheBlossomAlgorithmForMaximumMatching/.

Micali, S. and V.V. Vazirani, V. V. "An  Algorithm for Finding Maximum Matching in General Graphs." In Proc. 21st FOCS, pp. 17-27, 1980.

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

Vazirani, V. V. "A Theory of Alternating Paths and Blossoms for Proving Correctness of the  General Graph Maximum Matching Algorithm." Combinatorica 14, 71-109, 1994.

West, D. B. "Edmonds' Blossom Algorithm." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 142-145, 2000.