Blossom algorithm
Introduction 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.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  for the same task can be achieved with the much more complex algorithm of Micali and Vazirani.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. 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."
Augmenting paths 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 :.alt=Augmentation along a pathBy Berge's lemma, matching  is maximum if and only if there is no -augmenting path in . 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.
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:'''''* Traverse the graph starting from an exposed vertex. * Starting from that vertex, label it as an outer vertex . * Alternate the labeling between vertices being inner   and outer  such that no two adjacent vertices have the same label. * If we end up with two adjacent vertices labeled as outer   then we have an odd-length cycle and hence a blossom.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 .alt=Example of a blossom 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:* if  traverses through a segment  in , then this segment is replaced with the segment  in , where blossom vertices  and  and the side of , , going from  to  are chosen to ensure that the new path is still alternating ( is exposed with respect to , ).alt=Path lifting when  traverses through , two cases depending on the direction we need to choose to reach * if  has an endpoint , then the path segment  in  is replaced with the segment  in , where blossom vertices  and  and the side of , , going from  to  are chosen to ensure that the path is alternating ( is exposed, ).alt=Path lifting when  ends at , two cases depending on the direction we need to choose to reach Thus blossoms can be contracted and search performed in the contracted graphs. This reduction is at the heart of Edmonds' algorithm.
Finding an augmenting path 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 { ''v'' } 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'' = { ''v'', ''w'' } '''do''' B10            '''if''' ''w'' is not in ''F'' '''then'''                    // ''w'' is matched, so add ''e'' and ''w'''s matched edge to ''F'' B11                ''x'' ← vertex matched to ''w'' in ''M'' B12                add edges { ''v'', ''w'' } and { ''w'', ''x'' } 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  { ''e'' }. B17                        ''P'' ← path (''root''(''v'') → ... → ''v'') → (''w'' → ... → ''root''(''w'')) B18                        '''return''' ''P'' B19                    '''else'''                            // Contract a blossom in ''G'' and look for the path in the contracted graph. B20                        ''B'' ← blossom formed by ''e'' and edges on the path ''v'' → ''w'' in ''T'' B21                        ''G’, M’'' ← contract ''G'' and ''M'' by ''B'' B22                        ''P’'' ← ''find_augmenting_path''(''G’'', ''M’'') B23                        ''P'' ← lift ''P’'' to ''G'' B24                        '''return''' ''P'' B25                    '''end if''' B26                '''end if''' B27            '''end if''' B28            mark edge ''e'' B29        '''end while''' B30        mark vertex ''v'' B31    '''end while''' B32    '''return''' empty path B33 '''end function'''===Examples===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).alt=Forest expansion on line B10Next, it detects a blossom and contracts the graph (lines B20 – B21).alt=Blossom contraction on line B21Finally, 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.alt=Detection of augmenting path  in  on line B17alt=Lifting of  to corresponding augmenting path in  on line B25===Analysis===The forest  constructed by the  function is an alternating forest. * a tree  in  is an '''alternating tree''' with respect to , if**  contains exactly one exposed vertex  called the tree root** every vertex at an odd distance from the root has exactly two incident edges in , and** all paths from  to leaves in  have even lengths, their odd edges are not in  and their even edges are in . * a forest  in  is an '''alternating forest''' with respect to , if** its connected components are alternating trees, and** every exposed vertex in  is a root of an alternating tree in .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 .===Bipartite matching===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.===Weighted matching===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. Kolmogorov provides an efficient C++ implementation of this.
References