In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965.[1] Given a general graph, the algorithm finds a matching such that each vertex in is incident with at most one edge in and is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.
The algorithm runs in time, where is the number of edges of the graph and is its number of vertices. A better running time of
O(|E|\sqrt{|V|})
A major reason that the blossom algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time. Another reason is that it led to a linear programming polyhedral description of the matching polytope, yielding an algorithm for min-weight matching.[3] As elaborated by Alexander Schrijver, further significance of the result comes from the fact that this was the first polytope whose proof of integrality "does not simply follow just from total unimodularity, and its description was a breakthrough in polyhedral combinatorics."[4]
Given and a matching of, a vertex is exposed if no edge of is incident with . A path in is an alternating path, if its edges are alternately not in and in (or in and not in). An augmenting path is an alternating path that starts and ends at two distinct exposed vertices. Note that the number of unmatched edges in an augmenting path is greater by one than the number of matched edges, and hence the total number of edges in an augmenting path is odd. A matching augmentation along an augmenting path is the operation of replacing with a new matching
M1=M ⊕ P=(M\setminusP)\cup(P\setminusM)
By Berge's lemma, matching is maximum if and only if there is no -augmenting path in .[5] Hence, either a matching is maximum, or it can be augmented. Thus, starting from an initial matching, we can compute a maximum matching by augmenting the current matching with augmenting paths as long as we can find them, and return whenever no augmenting paths are left. We can formalize the algorithm as follows:
INPUT: Graph G, initial matching M on G OUTPUT: maximum matching M* on G A1 function find_maximum_matching(G, M) : M* A2 P ← find_augmenting_path(G, M) A3 if P is non-empty then A4 return find_maximum_matching(G, augment M along P) A5 else A6 return M A7 end if A8 end function
We still have to describe how augmenting paths can be found efficiently. The subroutine to find them uses blossoms and contractions.
Given and a matching of, a blossom is a cycle in consisting of edges of which exactly belong to, and where one of the vertices of the cycle (the base) is such that there exists an alternating path of even length (the stem) from to an exposed vertex .
Finding Blossoms:
Define the contracted graph as the graph obtained from by contracting every edge of, and define the contracted matching as the matching of corresponding to .
has an -augmenting path if and only if has an -augmenting path, and that any -augmenting path in can be lifted to an -augmenting path in by undoing the contraction by so that the segment of (if any) traversing through is replaced by an appropriate segment traversing through . In more detail:
M\capB
\{w',w\}\inE\setminusM
\{u',u\}\inE\setminusM
Thus blossoms can be contracted and search performed in the contracted graphs. This reduction is at the heart of Edmonds' algorithm.
The search for an augmenting path uses an auxiliary data structure consisting of a forest whose individual trees correspond to specific portions of the graph . In fact, the forest is the same that would be used to find maximum matchings in bipartite graphs (without need for shrinking blossoms).In each iteration the algorithm either (1) finds an augmenting path, (2) finds a blossom and recurses onto the corresponding contracted graph, or (3) concludes there are no augmenting paths. The auxiliary structure is built by an incremental procedure discussed next.
The construction procedure considers vertices and edges in and incrementally updates as appropriate. If is in a tree of the forest, we let denote the root of . If both and are in the same tree in, we let denote the length of the unique path from to in .
INPUT: Graph G, matching M on G OUTPUT: augmenting path P in G or empty path if none found B01 function find_augmenting_path(G, M) : P B02 F ← empty forest B03 unmark all vertices and edges in G, mark all edges of M B05 for each exposed vertex v do B06 create a singleton tree and add the tree to F B07 end for B08 while there is an unmarked vertex v in F with distance(v, root(v)) even do B09 while there exists an unmarked edge e = do B10 if w is not in F then // w is matched, so add e and ws matched edge to F B11 x ← vertex matched to w in M B12 add edges and to the tree of v B13 else B14 if distance(w, root(w)) is odd then // Do nothing. B15 else B16 if root(v) ≠ root(w) then // Report an augmenting path in F
\cup
The following four figures illustrate the execution of the algorithm. Dashed lines indicate edges that are currently not present in the forest. First, the algorithm processes an out-of-forest edge that causes the expansion of the current forest (lines B10 - B12).
Next, it detects a blossom and contracts the graph (lines B20 - B21).
Finally, it locates an augmenting path in the contracted graph (line B22) and lifts it to the original graph (line B23). Note that the ability of the algorithm to contract blossoms is crucial here; the algorithm cannot find in the original graph directly because only out-of-forest edges between vertices at even distances from the roots are considered on line B17 of the algorithm.
The forest constructed by the function is an alternating forest.
Each iteration of the loop starting at line B09 either adds to a tree in (line B10) or finds an augmenting path (line B17) or finds a blossom (line B20). It is easy to see that the running time is
O(|E||V|2)
When is bipartite, there are no odd cycles in . In that case, blossoms will never be found and one can simply remove lines B20 - B24 of the algorithm. The algorithm thus reduces to the standard algorithm to construct maximum cardinality matchings in bipartite graphs where we repeatedly search for an augmenting path by a simple graph traversal: this is for instance the case of the Ford–Fulkerson algorithm.
The matching problem can be generalized by assigning weights to edges in and asking for a set that produces a matching of maximum (minimum) total weight: this is the maximum weight matching problem. This problem can be solved by a combinatorial algorithm that uses the unweighted Edmonds's algorithm as a subroutine.[5] Kolmogorov provides an efficient C++ implementation of this.