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.