The Blossom Algorithm for Maximum Matching
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).