Blossom algorithm

Blossoms and contractions

Given G = (V, E) and a matching M of G, a blossom B is a cycle in G consisting of 2k + 1 edges of which exactly k belong to M, and where one of the vertices v of the cycle (the base) is such that there exists an alternating path of even length (the stem) from v to an exposed vertex w.

Finding Blossoms:

• Traverse the graph starting from an exposed vertex.
• Starting from that vertex, label it as an outer vertex o.
• Alternate the labeling between vertices being inner i and outer o such that no two adjacent vertices have the same label.
• If we end up with two adjacent vertices labeled as outer o then we have an odd-length cycle and hence a blossom.

Define the contracted graph G' as the graph obtained from G by contracting every edge of B, and define the contracted matching M' as the matching of G' corresponding to M.

G' has an M'-augmenting path if and only if 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 v_B is replaced by an appropriate segment traversing through B. In more detail:

• if P' traverses through a segment u → v_B → w in G', then this segment is replaced with the segment u → ( u' → … → w' ) → w in G, where blossom vertices u' and w' and the side of B, ( u' → … → w' ), going from u' to w' are chosen to ensure that the new path is still alternating (u' is exposed with respect to ${\displaystyle M\cap B}$, ${\displaystyle \{w^{\prime },w\}\in E\setminus M}$).

• if P' has an endpoint v_B, then the path segment u → v_B in G' is replaced with the segment u → ( u' → … → v' ) in G, where blossom vertices u' and v' and the side of B, ( u' → … → v' ), going from u' to v' are chosen to ensure that the path is alternating (v' is exposed, ${\displaystyle \{u^{\prime },u\}\in E\setminus M}$).

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 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 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 v and edges e in G and incrementally updates F as appropriate. If v is in a tree T of the forest, we let root(v) denote the root of T. If both u and v are in the same tree T in F, we let distance(u,v) denote the length of the unique path from u to v in T.

INPUT: Graph <i id="mwAQU">G</i>, matching <i id="mwAQY">M</i> on <i id="mwAQc">G</i> OUTPUT: augmenting path <i id="mwAQg">P</i> in <i id="mwAQk">G</i> or empty path if none found B01 <b id="mwAQo">function</b> <i id="mwAQs">find_augmenting_path</i>(<i id="mwAQw">G</i>, <i id="mwAQ0">M</i>) : <i id="mwAQ4">P</i> B02 <i id="mwAQ8">F</i> ← empty forest B03 unmark all vertices and edges in <i id="mwARA">G</i>, mark all edges of <i id="mwARE">M</i> B05 <b id="mwARI">for each</b> exposed vertex <i id="mwARM">v</i> <b id="mwARQ">do</b> B06 create a singleton tree { <i id="mwARU">v</i> } and add the tree to <i id="mwARY">F</i> B07 <b id="mwARc">end for</b> B08 <b id="mwARg">while</b> there is an unmarked vertex <i id="mwARk">v</i> in <i id="mwARo">F</i> with <i id="mwARs">distance(v, root(v))</i> even <b id="mwARw">do</b> B09 <b id="mwAR0">while</b> there exists an unmarked edge <i id="mwAR4">e</i> = { <i id="mwAR8">v</i>, <i id="mwASA">w</i> } <b id="mwASE">do</b> B10 <b id="mwASI">if</b> <i id="mwASM">w</i> is not in <i id="mwASQ">F</i> <b id="mwASU">then</b> // <i id="mwASY">w</i> is matched, so add <i id="mwASc">e</i> and <i id="mwASg">w'</i>s matched edge to <i id="mwASk">F</i> B11 <i id="mwASo">x</i> ← vertex matched to <i id="mwASs">w</i> in <i id="mwASw">M</i> B12 add edges { <i id="mwAS0">v</i>, <i id="mwAS4">w</i> } and { <i id="mwAS8">w</i>, <i id="mwATA">x</i> } to the tree of <i id="mwATE">v</i> B13 <b id="mwATI">else</b> B14 <b id="mwATM">if</b> <i id="mwATQ">distance(w, root(w))</i> is odd <b id="mwATU">then</b> // Do nothing. B15 <b id="mwATY">else</b> B16 <b id="mwATc">if</b> <i id="mwATg">root(v)</i> ≠ <i id="mwATk">root(w)</i> <b id="mwATo">then</b> // Report an augmenting path in F <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt145" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\cup"}}' id="mwATs"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \cup }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>∪<!-- ∪ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \cup }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e8ff7d0293ad19b43524a133ae5129f3d71f2040" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \cup }"/></span> { <i id="mwATw">e</i> }. B17 <i id="mwAT0">P</i> ← path (<i id="mwAT4">root</i>(<i id="mwAT8">v</i>) → ... → <i id="mwAUA">v</i>) → (<i id="mwAUE">w</i> → ... → <i id="mwAUI">root</i>(<i id="mwAUM">w</i>)) B18 <b id="mwAUQ">return</b> <i id="mwAUU">P</i> B19 <b id="mwAUY">else</b> // Contract a blossom in <i id="mwAUc">G</i> and look for the path in the contracted graph. B20 <i id="mwAUg">B</i> ← blossom formed by <i id="mwAUk">e</i> and edges on the path <i id="mwAUo">v</i> → <i id="mwAUs">w</i> in <i id="mwAUw">T</i> B21 <i id="mwAU0">G’, M’</i> ← contract <i id="mwAU4">G</i> and <i id="mwAU8">M</i> by <i id="mwAVA">B</i> B22 <i id="mwAVE">P’</i> ← <i id="mwAVI">find_augmenting_path</i>(<i id="mwAVM">G’</i>, <i id="mwAVQ">M’</i>) B23 <i id="mwAVU">P</i> ← lift <i id="mwAVY">P’</i> to <i id="mwAVc">G</i> B24 <b id="mwAVg">return</b> <i id="mwAVk">P</i> B25 <b id="mwAVo">end if</b> B26 <b id="mwAVs">end if</b> B27 <b id="mwAVw">end if</b> B28 mark edge <i id="mwAV0">e</i> B29 <b id="mwAV4">end while</b> B30 mark vertex <i id="mwAV8">v</i> B31 <b id="mwAWA">end while</b> B32 <b id="mwAWE">return</b> empty path B33 <b id="mwAWI">end function</b>

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).

Next, it detects a blossom and contracts the graph (lines B20 – B21).

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.

Analysis

The forest F constructed by the find_augmenting_path() function is an alternating forest.

• a tree T in G is an alternating tree with respect to M, if
  • T contains exactly one exposed vertex r called the tree root
  • every vertex at an odd distance from the root has exactly two incident edges in T, and
  • 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.
• a forest F in G is an alternating forest with respect to M, if
  • its connected components are alternating trees, and
  • every exposed vertex in G is a root of an alternating tree in F.

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 ${\displaystyle O(|E||V{|}^2)}$.

Parallelization

The Blossom algorithm is difficult to parallelize for several reasons. First, blossom contraction and lifting recursively change the graph structure, creating sequential dependencies between different stages of the search. Second, a standard search iteration usually finds only one augmenting path, increasing the matching size by one at a time and requiring many iterations on large graphs. Third, the algorithm maintains dynamic structures, including alternating trees and contracted graphs, that are repeatedly updated during execution. In a parallel implementation, these updates may require synchronization and can introduce data races. These factors have made efficient parallel implementations of the Blossom algorithm highly challenging.

X-Blossom provides an effective parallel solution for computing maximum matchings in general graphs and directly addresses these challenges. It first introduces a new recursion-free Blossom algorithm. In the traditional algorithm, a blossom is contracted during the search and later lifted when an augmenting path is found. By contrast, the recursion-free algorithm eliminates this contraction-and-lifting process. The key observation is that, when constructing an augmenting path, preserving the full recursive contraction history is unnecessary. The essential information is the appropriate even-length path through the blossom structure. Thus, instead of contracting a blossom and later expanding it, the recursion-free algorithm records the even-length path from each relevant vertex on a blossom cycle to the base of the blossom. When an augmenting path passes through the blossom, the recorded path is used to reconstruct the corresponding path in the original graph, as shown in the figure below. This representation preserves the effect of blossom handling while keeping the graph structure static during the search.

This recursion-free variant exposes a critical opportunity for massive parallelization. Since the graph is not recursively modified by contraction and lifting, multiple valid vertices in the current search forest can be examined concurrently. X-Blossom uses this property to identify multiple vertex-disjoint augmenting paths in a single search iteration, allowing the matching size to increase by more than one per iteration.

In its implementation, X-Blossom further replaces alternating-tree structures with a path table. This table records even-length paths for vertices, regardless of whether they belong to a blossom. As a result, the algorithm avoids repeatedly constructing and deconstructing alternating trees and contracted graphs. This reduces path-tracing overhead and makes the algorithm more suitable for parallel execution. Experiments reported in the X-Blossom study showed that its recursion-free design significantly improves the sequential performance, and its parallel version achieves speedups and scalability on multicore platforms across both real-world and synthetic datasets.

Bipartite matching

When G is bipartite, 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 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 G and asking for a matching of maximum total weight: this is known as the maximum weight matching problem. This problem can be solved by a combinatorial algorithm that uses the unweighted blossom algorithm as a subroutine. Efficient, polynomial-time algorithms for this problem are available in several software libraries, including NetworkX, LEDA, and the LEMON graph library.