Blossom algorithm: Difference between revisions

Revision as of 06:51, 8 July 2022

Latest revision as of 02:10, 26 June 2025

(6 intermediate revisions by 5 users not shown)

Line 19:

| 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

Line 84 ⟶ 85:

==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

Line 103 ⟶ 104:

}}</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.

Line 214 ⟶ 215:

<references/>

{{DEFAULTSORT:Edmonds's Matching Algorithm}}

[[Category:Graph algorithms]]

[[Category:Matching (graph theory)]]