|
| year = 1965
| pages = 449–467
| doi-access = free
}}</ref> Given a general [[Graph (discrete mathematics)|graph]] {{math|1=''G'' = (''V'', ''E'')}}, the algorithm finds a matching {{mvar|M}} such that each vertex in {{mvar|V}} is incident with at most one edge in {{mvar|M}} and {{math|{{abs|''M''}}}} is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike [[bipartite graph|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 {{math|[[Big O notation|''O'']]({{abs|''E''}}{{abs|''V''}}{{sup|2}})}}, where {{math|{{abs|''E''}}}} is the number of [[edge (graph)|edges]] of the graph and {{math|{{abs|''V''}}}} is its number of [[vertex (graph)|vertices]]. A better running time of <math>O( |E| \sqrt{ |V| } )</math> for the same task can be achieved with the much more complex algorithm of Micali and Vazirani.<ref name = "micali">{{cite conference
==Blossoms and contractions==
Given {{math|1=''G'' = (''V'', ''E'')}} and a matching ''{{mvar|M''}} of ''{{mvar|G''}}, a ''[[blossom (graph theory)|blossom]]'' ''{{mvar|B''}} is a cycle in ''{{mvar|G''}} consisting of {{math|2''k''2k + 1''}} edges of which exactly ''{{mvar|k''}} belong to ''{{mvar|M''}}, and where one of the vertices ''{{mvar|v''}} of the cycle (the ''base'') is such that there exists an alternating path of even length (the ''stem'') from ''{{mvar|v''}} to an exposed vertex ''{{mvar|w''}}.
'''''Finding Blossoms:'''''
* Traverse the graph starting from an exposed vertex.
* Starting from that vertex, label it as an outer vertex "''{{mvar|'''o'''"''}}.
* Alternate the labeling between vertices being inner "''{{mvar|'''i'''"''}} and outer "''{{mvar|'''o'''"''}} such that no two adjacent vertices have the same label.
* If we end up with two adjacent vertices labeled as outer "''{{mvar|'''o'''"''}} then we have an odd-length cycle and hence a blossom.
Define the '''contracted graph''' {{mvar|G''G’''}} as the graph obtained from ''{{mvar|G''}} by [[edge contraction|contracting]] every edge of ''{{mvar|B''}}, and define the '''contracted matching''' {{mvar|M''M’''}} as the matching of {{mvar|G''G’''}} corresponding to ''{{mvar|M''}}.
[[File:Edmonds blossom.svg|500px|alt=Example of a blossom]]
{{mvar|G''G’''}} has an {{mvar|M''M’''}}-augmenting path [[if and only if]] ''{{mvar|G''}} has an ''{{mvar|M''}}-augmenting path, and that any {{mvar|M''M’''}}-augmenting path {{mvar|P''P’''}} in {{mvar|G''G’''}} can be '''lifted''' to an ''{{mvar|M''}}-augmenting path in ''{{mvar|G''}} by undoing the contraction by ''{{mvar|B''}} so that the segment of {{mvar|P''P’''}} (if any) traversing through ''{{mvar|v<{{sub>|B</sub>''}}}} is replaced by an appropriate segment traversing through ''{{mvar|B''}}.<ref name = "tarjan notes">{{citation
| author = Tarjan, Robert
| contribution = Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching
}}</ref> In more detail:
* if {{mvar|P''P’''}} traverses through a segment {{math|''u'' → ''v<{{sub>|B</sub>}}'' → ''w''}} in {{mvar|G''G’''}}, then this segment is replaced with the segment {{math|''u'' → ( u’''u''' → ...… → w’''w' '' ) → ''w''}} in ''{{mvar|G''}}, where blossom vertices {{mvar|u''u’''}} and {{mvar|w''w’''}} and the side of ''{{mvar|B}}, {{math|( '',u' ''( u’ → ...… → w’''w' )'' )}}, going from {{mvar|u''u’''}} to {{mvar|w''w’''}} are chosen to ensure that the new path is still alternating ({{mvar|u''u’''}} is exposed with respect to <math>M \cap B</math>, <math>\{ w', w \} \in E \setminus M</math>).
[[File:Edmonds lifting path.svg|500px|alt=Path lifting when {{mvar|P''P’''}} traverses through ''{{mvar|v<{{sub>|B</sub>''}}}}, two cases depending on the direction we need to choose to reach ''{{mvar|v<{{sub>|B</sub>''}}}}]]
* if {{mvar|P''P’''}} has an endpoint ''{{mvar|v<{{sub>|B</sub>''}}}}, then the path segment {{math|''u'' → ''v<{{sub>|B</sub>}}''}} in {{mvar|G''G’''}} is replaced with the segment {{math|''u'' → ( u’''u' '' → ...… → v’''v' )'' )}} in ''{{mvar|G''}}, where blossom vertices {{mvar|u''u’''}} and {{mvar|v''v’''}} and the side of ''{{mvar|B''}}, {{math|( ''(u' u’'' → ...… → v’''v' )'' )}}, going from {{mvar|u''u’''}} to {{mvar|v''v’''}} are chosen to ensure that the path is alternating ({{mvar|v''v’''}} is exposed, <math>\{ u', u \} \in E \setminus M</math>).
[[File:Edmonds lifting end point.svg|500px|alt=Path lifting when {{mvar|P''P’''}} ends at ''{{mvar|v<{{sub>|B</sub>''}}}}, two cases depending on the direction we need to choose to reach ''{{mvar|v<{{sub>|B</sub>''}}}}]]
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 (graph theory)|forest]] ''{{mvar|F''}} whose individual trees correspond to specific portions of the graph ''{{mvar|G''}}. In fact, the forest ''{{mvar|F''}} is the same that would be used to find maximum matchings in [[bipartite graph]]s (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.<ref name = "tarjan notes"/>
The construction procedure considers vertices ''{{mvar|v''}} and edges ''{{mvar|e''}} in ''{{mvar|G''}} and incrementally updates ''{{mvar|F''}} as appropriate. If ''{{mvar|v''}} is in a tree ''{{mvar|T''}} of the forest, we let ''{{code|root(v)}}'' denote the root of ''{{mvar|T''}}. If both ''{{mvar|u''}} and ''{{mvar|v''}} are in the same tree ''{{mvar|T''}} in ''{{mvar|F''}}, we let ''{{code|distance(u,v)}}'' denote the length of the unique path from ''{{mvar|u''}} to ''{{mvar|v''}} in ''{{mvar|T''}}.
INPUT: Graph ''G'', matching ''M'' on ''G''
[[File:blossom contraction.png|400px|alt=Blossom contraction on line B21]]
Finally, it locates an augmenting path {{mvar|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 ''{{mvar|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.
[[File:path detection.png|400px|alt=Detection of augmenting path {{mvar|P′}} in {{mvar|G′}} on line B17]]
[[File:path lifting.png|400px|alt=Lifting of {{mvar|P′}} to corresponding augmenting path in {{mvar|G}} on line B25]]
===Analysis===
The forest ''{{mvar|F''}} constructed by the ''{{code|find_augmenting_path()''}} function is an alternating forest.<ref name = "kenyon report">{{citation
| author1 = Kenyon, Claire
| author2 = Lovász, László
| title = Technical Report CS-TR-251-90, Department of Computer Science, Princeton University
}}</ref>
* a tree ''{{mvar|T''}} in ''{{mvar|G''}} is an '''alternating tree''' with respect to ''{{mvar|M''}}, if
** ''{{mvar|T''}} contains exactly one exposed vertex ''{{mvar|r''}} called the tree root
** every vertex at an odd distance from the root has exactly two incident edges in ''{{mvar|T''}}, and
** all paths from ''{{mvar|r''}} to leaves in ''{{mvar|T''}} have even lengths, their odd edges are not in ''{{mvar|M''}} and their even edges are in ''{{mvar|M''}}.
* a forest ''{{mvar|F''}} in ''{{mvar|G''}} is an '''alternating forest''' with respect to ''{{mvar|M''}}, if
** its connected components are alternating trees, and
** every exposed vertex in ''{{mvar|G''}} is a root of an alternating tree in ''{{mvar|F''}}.
Each iteration of the loop starting at line B09 either adds to a tree ''{{mvar|T''}} in ''{{mvar|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 <math>O( |E||V|^2)</math>.
===Bipartite matching===
When ''{{mvar|G''}} is [[bipartite graph|bipartite]], there are no odd cycles in ''{{mvar|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<ref name = "karp notes"/> 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 ''{{mvar|G''}} and asking for a set ''{{mvar|M''}} 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.<ref name = "matching book"/> Kolmogorov provides an efficient C++ implementation of this.<ref name = blossom5>{{citation
| author = Kolmogorov, Vladimir
| title = Blossom V: A new implementation of a minimum cost perfect matching algorithm
<references/>
{{DEFAULTSORT:Edmonds's Matching Algorithm}}
[[Category:Graph algorithms]]
[[Category:Matching (graph theory)]]
| 