Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Blossom algorithm
open-in-new
<h2 id="augmenting-paths">Augmenting paths</h2> <p>Given <i>G</i> = (<i>V</i>, <i>E</i>) and a matching M of G, a vertex v is exposed if no edge of M is incident with v. A path in G is an alternating path, if its edges are alternately not in M and in M (or in M and not in M). An augmenting path P 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 P is the operation of replacing M with a new matching </p> M 1 = M ⊕ P = ( M ∖ P ) ∪ ( P ∖ M ) {\displaystyle M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)} . <p>By <a href="/facts/Berge%2527s_lemma/13jr1Bmc">Berge's lemma</a>, matching M is maximum if and only if there is no M-augmenting path in G.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> 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: </p> INPUT: Graph <i>G</i>, initial matching <i>M</i> on <i>G</i> OUTPUT: maximum matching <i>M*</i> on <i>G</i> A1 function <i>find_maximum_matching</i>(<i>G</i>, <i>M</i>) : <i>M*</i> A2 <i>P</i> ← <i>find_augmenting_path</i>(<i>G</i>, <i>M</i>) A3 if <i>P</i> is non-empty then A4 return <i>find_maximum_matching</i>(<i>G</i>, augment <i>M</i> along <i>P</i>) A5 else A6 return M A7 end if A8 end function <p>We still have to describe how augmenting paths can be found efficiently. The subroutine to find them uses blossoms and contractions. </p> <h2 id="blossoms-and-contractions">Blossoms and contractions</h2> <p>Given <i>G</i> = (<i>V</i>, <i>E</i>) and a matching M of G, a <i><a href="/facts/Blossom_(graph_theory)/CT2eT98n">blossom</a></i> B is a cycle in G consisting of 2<i>k</i> + 1 edges of which exactly k belong to M, and where one of the vertices v of the cycle (the <i>base</i>) is such that there exists an alternating path of even length (the <i>stem</i>) from v to an exposed vertex w. </p><p><i>Finding Blossoms:</i> </p> <ul><li>Traverse the graph starting from an exposed vertex.</li> <li>Starting from that vertex, label it as an outer vertex o.</li> <li>Alternate the labeling between vertices being inner i and outer o such that no two adjacent vertices have the same label.</li> <li>If we end up with two adjacent vertices labeled as outer o then we have an odd-length cycle and hence a blossom.</li></ul> <p>Define the contracted graph G' as the graph obtained from G by <a href="/facts/Edge_contraction/PRqKXEkj">contracting</a> every edge of B, and define the contracted matching M' as the matching of G' corresponding to M. </p><p>G' has an M'-augmenting path <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> G has an M-augmenting path, and that any M'-augmenting path P' in G' can be lifted to an M-augmenting path in G by undoing the contraction by B so that the segment of P' (if any) traversing through vB is replaced by an appropriate segment traversing through B.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> In more detail: </p> <ul><li>if P' traverses through a segment <i>u</i> → <i>vB</i> → <i>w</i> in G', then this segment is replaced with the segment <i>u</i> → ( <i>u'</i> → … → <i>w' </i> ) → <i>w</i> in G, where blossom vertices u' and w' and the side of B, ( <i>u' </i> → … → <i>w' </i> ), going from u' to w' are chosen to ensure that the new path is still alternating (u' is exposed with respect to M ∩ B {\displaystyle M\cap B} , { w ′ , w } ∈ E ∖ M {\displaystyle \{w',w\}\in E\setminus M} ).</li></ul> <ul><li>if P' has an endpoint vB, then the path segment <i>u</i> → <i>vB</i> in G' is replaced with the segment <i>u</i> → ( <i>u' </i> → … → <i>v' </i> ) in G, where blossom vertices u' and v' and the side of B, ( <i>u' </i> → … → <i>v' </i> ), going from u' to v' are chosen to ensure that the path is alternating (v' is exposed, { u ′ , u } ∈ E ∖ M {\displaystyle \{u',u\}\in E\setminus M} ).</li></ul> <p>Thus blossoms can be contracted and search performed in the contracted graphs. This reduction is at the heart of Edmonds' algorithm. </p> <h2 id="finding-an-augmenting-path">Finding an augmenting path</h2> <p>The search for an augmenting path uses an auxiliary data structure consisting of a <a href="/facts/Forest_(graph_theory)/TCWk4Joy">forest</a> F whose individual trees correspond to specific portions of the graph G. In fact, the forest F is the same that would be used to find maximum matchings in <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a> (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.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p><p>The construction procedure considers vertices v and edges e in G and incrementally updates F as appropriate. If v is in a tree T of the forest, we let <i>root(v)</i> denote the root of T. If both u and v are in the same tree T in F, we let <i>distance(u,v)</i> denote the length of the unique path from u to v in T. </p> INPUT: Graph <i>G</i>, matching <i>M</i> on <i>G</i> OUTPUT: augmenting path <i>P</i> in <i>G</i> or empty path if none found B01 function <i>find_augmenting_path</i>(<i>G</i>, <i>M</i>) : <i>P</i> B02 <i>F</i> ← empty forest B03 unmark all vertices and edges in <i>G</i>, mark all edges of <i>M</i> B05 for each exposed vertex <i>v</i> do B06 create a singleton tree { <i>v</i> } and add the tree to <i>F</i> B07 end for B08 while there is an unmarked vertex <i>v</i> in <i>F</i> with <i>distance(v, root(v))</i> even do B09 while there exists an unmarked edge <i>e</i> = { <i>v</i>, <i>w</i> } do B10 if <i>w</i> is not in <i>F</i> then // <i>w</i> is matched, so add <i>e</i> and <i>w'</i>s matched edge to <i>F</i> B11 <i>x</i> ← vertex matched to <i>w</i> in <i>M</i> B12 add edges { <i>v</i>, <i>w</i> } and { <i>w</i>, <i>x</i> } to the tree of <i>v</i> B13 else B14 if <i>distance(w, root(w))</i> is odd then // Do nothing. B15 else B16 if <i>root(v)</i> ≠ <i>root(w)</i> then // Report an augmenting path in F ∪ {\displaystyle \cup } { <i>e</i> }. B17 <i>P</i> ← path (<i>root</i>(<i>v</i>) → ... → <i>v</i>) → (<i>w</i> → ... → <i>root</i>(<i>w</i>)) B18 return <i>P</i> B19 else // Contract a blossom in <i>G</i> and look for the path in the contracted graph. B20 <i>B</i> ← blossom formed by <i>e</i> and edges on the path <i>v</i> → <i>w</i> in <i>T</i> B21 <i>G’, M’</i> ← contract <i>G</i> and <i>M</i> by <i>B</i> B22 <i>P’</i> ← <i>find_augmenting_path</i>(<i>G’</i>, <i>M’</i>) B23 <i>P</i> ← lift <i>P’</i> to <i>G</i> B24 return <i>P</i> B25 end if B26 end if B27 end if B28 mark edge <i>e</i> B29 end while B30 mark vertex <i>v</i> B31 end while B32 return empty path B33 end function <h3>Examples</h3> <p>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). </p><p>Next, it detects a blossom and contracts the graph (lines B20 – B21). </p><p>Finally, it locates an augmenting path P′ 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 P 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. </p> <h3>Analysis</h3> <p>The forest F constructed by the find_augmenting_path() function is an alternating forest.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <ul><li>a tree T in G is an alternating tree with respect to M, if <ul><li>T contains exactly one exposed vertex r called the tree root</li> <li>every vertex at an odd distance from the root has exactly two incident edges in T, and</li> <li>all paths from r to leaves in T have even lengths, their odd edges are not in M and their even edges are in M.</li></ul></li> <li>a forest F in G is an alternating forest with respect to M, if <ul><li>its connected components are alternating trees, and</li> <li>every exposed vertex in G is a root of an alternating tree in F.</li></ul></li></ul> <p>Each iteration of the loop starting at line B09 either adds 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 is O ( | E | | V | 2 ) {\displaystyle O(|E||V|^{2})} . </p> <h3>Bipartite matching</h3> <p>When G is <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a>, there are no odd cycles in G. 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<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> where we repeatedly search for an augmenting path by a simple graph traversal: this is for instance the case of the <a href="/facts/Ford%25E2%2580%2593Fulkerson_algorithm/wwk3tw52">Ford–Fulkerson algorithm</a>. </p> <h3>Weighted matching</h3> <p>The matching problem can be generalized by assigning weights to edges in G and asking for a set M that produces a matching of maximum (minimum) total weight: this is the <a href="/facts/Maximum_weight_matching/5H8UBkJb">maximum weight matching</a> problem. This problem can be solved by a combinatorial algorithm that uses the unweighted Edmonds's algorithm as a subroutine.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> Kolmogorov provides an efficient C++ implementation of this.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Edmonds, Jack (1991), "A glimpse of heaven", in J.K. Lenstra; A.H.G. Rinnooy Kan; A. Schrijver (eds.), History of Mathematical Programming --- A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland, Amsterdam, pp. 32–54 <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi:10.4153/CJM-1965-045-4. <a href="https://doi.org/10.4153%2FCJM-1965-045-4" target="_blank">https://doi.org/10.4153%2FCJM-1965-045-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Micali, Silvio; Vazirani, Vijay (1980). An O(V1/2E) algorithm for finding maximum matching in general graphs. 21st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, New York. pp. 17–27. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Edmonds, Jack (1965). "Maximum matching and a polyhedron with 0,1-vertices". Journal of Research of the National Bureau of Standards Section B. 69: 125–130. doi:10.6028/jres.069B.013. <a href="https://doi.org/10.6028%2Fjres.069B.013" target="_blank">https://doi.org/10.6028%2Fjres.069B.013</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Berlin Heidelberg: Springer-Verlag. ISBN 9783540443896. <a href="9783540443896" target="_blank">9783540443896</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Lovász, László; Plummer, Michael (1986). Matching Theory. Akadémiai Kiadó. ISBN 963-05-4168-8. <a href="963-05-4168-8" target="_blank">963-05-4168-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Karp, Richard, "Edmonds's Non-Bipartite Matching Algorithm", Course Notes. U. C. Berkeley (PDF), archived from the original (PDF) on 2008-12-30 <a href="https://web.archive.org/web/20081230183603/http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf" target="_blank">https://web.archive.org/web/20081230183603/http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Tarjan, Robert, "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching", Course Notes, Department of Computer Science, Princeton University (PDF) <a href="http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf" target="_blank">http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Tarjan, Robert, "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching", Course Notes, Department of Computer Science, Princeton University (PDF) <a href="http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf" target="_blank">http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Kenyon, Claire; Lovász, László, "Algorithmic Discrete Mathematics", Technical Report CS-TR-251-90, Department of Computer Science, Princeton University <a href="/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz" target="_blank">/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Karp, Richard, "Edmonds's Non-Bipartite Matching Algorithm", Course Notes. U. C. Berkeley (PDF), archived from the original (PDF) on 2008-12-30 <a href="https://web.archive.org/web/20081230183603/http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf" target="_blank">https://web.archive.org/web/20081230183603/http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Lovász, László; Plummer, Michael (1986). Matching Theory. Akadémiai Kiadó. ISBN 963-05-4168-8. <a href="963-05-4168-8" target="_blank">963-05-4168-8</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm", Mathematical Programming Computation, 1 (1): 43–67, doi:10.1007/s12532-009-0002-8 <a href="http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html" target="_blank">http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> </ol>