Lecture
The blossom algorithm (English Blossom algorithm) — is an algorithm in graph theory for constructing maximum matchings in graphs. The algorithm was developed by Jack Edmonds in 1961 and published in 1965 . Given a general graph G=(V, E), the algorithm finds a matching M such that each vertex of V is incident to at most one edge of M and |M| is maximum. The matching is constructed by iteratively improving an initial empty matching along augmenting paths of the graph. Unlike bipartite matching, the key new idea was to contract an odd cycle in the graph (a blossom) into a single vertex and continue the search iteratively on the contracted graph.
The main reason why the blossom algorithm is important is that it gave the first proof that a maximum matching can be found in polynomial time. Another reason is that the method leads to a description of the linear-programming polytope for the matching polytope, which leads to an algorithm for minimum-weight matching . As Alexander Schrijver clarified, the further importance of the result follows from the fact that this polytope was the first whose integrality proof «did not simply follow from total unimodularity, and whose description was a breakthrough in the combinatorics of polytopes».
Given a graph G=(V, E) and a matching M for G, a vertex v is exposed (not covered by the matching) if there is no edge of M incident to v. A path in G is an alternating path if its edges alternately do not belong to M and are contained in M. An augmenting path P — is an alternating path that begins and ends at exposed vertices. Note that the number of vertices not belonging to the matching in an augmenting path is one greater than the number of edges belonging to the matching, and therefore the number of edges in an augmenting path is odd. Augmenting a matching along a path P — is the operation of replacing the set M with a new matching 
.
By Berge's lemma, a matching M is maximum if and only if there is no M-augmenting path in G . Consequently, either the matching is maximum, or it can be augmented. Thus, starting from some matching, we can compute a maximum matching by augmenting the current matching using an augmenting path. The algorithm can be formalized as follows
INPUT: Graph G, initial matching M on G OUTPUT: maximum matching M* on G A1 function find_maximum_matching(G, M) : M* A2find_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 need to describe how augmenting paths can be efficiently constructed. The subroutine for finding them uses blossoms and contraction.
Given a graph G=(V, E) and a matching M of the graph G, a blossom B — is a cycle in G consisting of 2k + 1 edges, of which exactly k belong to M, and in which there is a vertex v (the base) such that there exists an alternating path of even length (the stem) from v to an exposed vertex w.
Finding blossoms:
We define the contracted graph G’ as the graph obtained from G by contracting all edges of the blossom B, and we define the contracted matching M’ as the matching of the graph G’ corresponding to M.
G’ has an M’-augmenting path if and only if G has an M-augmenting path, and then any M’-augmenting path P’ in G’ can be lifted to an M-augmenting path in G by restoring the blossom B that was contracted earlier, so that the segment of the path P’ (if any) passing through vB is replaced by a suitable segment passing through B . In more detail:
in G’, then this segment is replaced by the segment 
in G, where the blossom vertices u’ and w’ and the side of the blossom B, 
, going from u’ to w’ are chosen so that the new path remains alternating (u’ is exposed with respect to 
, 
).
in G’ is replaced by the segment 
in G, where the blossom vertices u’ and v’ and the side of the blossom B, 
, going from u’ to v’, is chosen so that the path is alternating (v’ is exposed, 
).
Then the blossom can be contracted and the search can be continued on the contracted graphs. This contraction is the heart of Edmonds' algorithm.
The search for an augmenting path uses an additional data structure, a forest F, whose individual trees correspond to portions of the graph G. In fact, the forest F is the same as the one used for finding maximum matchings in bipartite graphs (without the need to contract blossoms). At each iteration the algorithm either (1) finds an augmenting path, or (2) finds a blossom and recurses into the contracted graph, or (3) concludes that no augmenting path exists. The additional structure is built by means of an incremental procedure, discussed below .
The construction procedure examines the vertices v and edges e of the graph G and incrementally updates F accordingly. If v is in a tree T of the forest, we denote by root(v) the root of the tree T. If both u and v lie in the same tree T in F, we denote by distance(u, v) the length of the unique path from u to v in the tree T.
INPUT: Graph G, matching M in G
OUTPUT: Augmenting path P in G or an empty path if no such path is found
B01 function find_augmenting_path(G, M):P
B02 
empty forest
B03 make all vertices and edges unmarked in G, mark all edges of M
B05 for each exposed vertex v do
B06 create a single-vertex tree {v} and add the tree to F
B07 end for
B08 while there is an unmarked vertex v in F with even distance(v, root(v)) do
B09 while there exists an unmarked edge e={v, w} do
B10 if w is not in F then
// w is in the matching, so we add the edge
// covering e and w to F
B11 
is matched with vertex w in M
B12 add edges {v,w} and {w,x} to the tree for 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 
.
B17 path (
)
B18 return P
B19 else
// Contract a blossom in G and search for a path in the contracted graph.
B20 
blossom formed by e and the edges of the path 
in T
B21 
contract G and M by contracting the blossom B
B22 
find_augmenting_path 
B23 lift P’ into 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
The following four figures illustrate the execution of the algorithm. Dashed lines show edges that at that moment are not represented in the forest. First the algorithm processes an edge not belonging to the forest, which leads to an extension of the current forest (lines B10 — B12).
Then a blossom is removed and the graph is contracted (lines B20 — B21).
Finally, the algorithm discovers an augmenting path P′ in the contracted graph (line B22) and lifts it in the original graph (line B23). Note that the algorithm's ability to contract blossoms is crucial here. The algorithm cannot find P in the original graph directly, since only non-forest edges between vertices at an even distance from the root are considered in line B17 of the algorithm.
The forest F built by the function find_augmenting_path() is an alternating forest .
Each iteration of the loop starting at line B09 either adds a vertex to a tree T in F (line B10), or finds an augmenting path (line B17), or finds a blossom (line B20). It is easy to see that the running time of the algorithm equals 
. Micali and Vazirani[10] showed an algorithm that builds a maximum matching in time 
.
The algorithm reduces to the standard algorithm for matchings in bipartite graphs if G is bipartite. Since in this case there are no odd cycles in G, blossoms will never be found, and one can simply remove lines B20 — B24 of the algorithm.
The matching problem can be generalized by assigning weights to the edges of the graph G. In this case one asks about a set M that gives a matching with maximum (minimum) total weight. The weighted matching problem can be solved by a combinatorial algorithm that uses Edmonds' unweighted algorithm as a subroutine . Vladimir Kolmogorov gave an efficient implementation of this algorithm in C++[11].
Consider an undirected unweighted graph G=⟨V,E⟩, where V — is the set of vertices, E — the set of edges. It is required to find a maximum matching in it.
Let us give an example on which Kuhn's algorithm will not work. Consider the graph G with the set of vertices V=1,2,3,4, and the set of edges —E=⟨1,2⟩,⟨2,3⟩,⟨3,1⟩,⟨2,4⟩ and let the edge ⟨2,3⟩ be taken into the matching. Then, when starting from the vertex 1, if the traversal first goes to the vertex 2, it will reach a dead end at the vertex 3, instead of finding the augmenting path 1−3−2−4. As can be seen in this example, the main problem is that when entering an odd-length cycle, the traversal may go around the cycle in the wrong direction.
| Theorem: |
|
Given a graph G, a matching M in G and a cycle Z of length 2k+1 containing k edges of the matching M and vertex-disjoint from the other edges of M. We construct a new graph G′ from the graph G by contracting the cycle Z to a single vertex, whereby all edges incident to the vertices of this cycle become incident to that vertex in the new graph. Then the matching M−E(Z), where E(z) — are the edges incident to the cycle, is maximum in G′ if and only if M — is a maximum matching in G
|
| Proof: |
| ▹ |
|
Suppose that M is not a maximum matching in G, then by the theorem on maximum matching and augmenting paths there exists an augmenting path with respect to M, namely P. If P does not intersect Z, then the path is augmenting with respect to M′ in the graph G′ as well, and hence M′ cannot be a maximum matching. Therefore suppose that the path P intersects Z. Note that at least one endpoint of the path P does not lie on Z; denote it by u. Then we traverse the path P, starting from u to the first encountered vertex on Z; denote it by v. Then, upon contracting the cycle Z, the segment P[u,v] maps to an augmenting path with respect to M′, that is M′ is not a maximum matching, which contradicts our assumption. Now suppose that M′ is not a maximum matching in the graph G′. Denote by N′ a matching in G′ of cardinality greater than M′. We restore the graph G, then N′ will correspond to some matching in G covering at most one vertex in Z. Consequently the matching N′ can be augmented, using the k edges of the cycle Z, and obtain a matching N of size |N|=|N′|+k>|M′|+k=|M|, that is M is not a maximum matching in G, and we reach a contradiction. Thus the theorem is proved. |
| ◃ |
For simplicity of description of the algorithm, let us introduce some definitions.
| Definition: |
| We will call a blossom B of a graph G its cycle of odd length.
By a blossom contraction we mean the graph G′ obtained from G by contracting the whole odd cycle into a single pseudo-vertex. All edges incident to the vertices of this cycle become incident to the pseudo-vertex in the new graph. The base of a blossom - is the vertex of the blossom into which an edge not belonging to the given blossom enters. |
Let us describe an algorithm that makes it possible to find a maximum matching for an arbitrary graph G. From Edmonds' theorem it is clear that it is necessary to consider a matching in the contracted graph, where it can be found, for example, by means of Kuhn's algorithm, and afterwards to restore the matching in the original graph.
The main difficulty is presented by the operations of contracting and restoring blossoms. To do this efficiently, for each vertex it is necessary to store a pointer to the base of the blossom to which it belongs, or to itself otherwise. Suppose that to find matchings in the contracted graph we use breadth-first search. Then at each iteration of the algorithm a breadth-first-search tree will be built, and the path in it to any vertex will be an alternating path starting from the root of this tree. We will put into the queue only those vertices whose distance from the root in the path tree is even. Also, for each vertex whose distance is odd, in the array of ancestors p[] it is necessary to store its ancestor — an even vertex. Note that if in the process of breadth-first search we come from the current vertex v to a vertex u such that it is a root or belongs to the matching and to the path tree, then both of these vertices belong to some blossom. Indeed, when these conditions are satisfied these vertices are even vertices, and consequently the distance from them to their lowest common ancestor has the same parity. We find the lowest common ancestor lca(u,v) of the vertices u, v, which is the base of the blossom. To find the cycle itself it is necessary to walk from the vertices u, v to the base of the blossom. We will not contract the blossom explicitly; we simply put into the breadth-first-search queue all the vertices belonging to the blossom. Also, for all even vertices (except the base) we assign as ancestor the neighboring vertex in the cycle, and for the vertices u and v we assign each other as ancestors. This will allow the blossom to be correctly restored in the case when, during the restoration of the augmenting path, we enter an odd vertex of the cycle.
In total there are V iterations, at each of which a breadth-first search is performed in O(E); in addition, blossom-contraction operations may occur — there may be O(V) of them. Blossom contraction runs in O(V), so the overall asymptotics of the algorithm will be O(V(E+V2))=O(V3).
write/read in the comments
[[b8625]]
Comments