The algorithm for finding a minimum weight matching is due to Jack Edmonds (1965; see [5]). It is noteworthy because at the time the problem was known to be solvable in polynomial time for bipartite graphs, but it was not clear that the general problem would yield as well. The unweighted case, where one seeks a matching of maximum size, is somewhat easier, and is described in [2].
Our implementation follows [1], but we consider only complete graphs and assume all weights are non-negative; this is fully general since false edges of large negative weight can always be added to make a graph complete. We give enough details for the reader to understand the output. For further details of some of the steps, see [1]. Open-source code that implements the algorithm in an efficient way is available at [3].
We assume the reader is familiar with the basics of matching theory in the bipartite case (see [4]); the main idea there is that of building an alternating-path tree and using the tree to augment the matching one edge at a time. For the weighted bipartite case, we use the idea of a feasible labeling
of the vertices, where "feasible" means that for any edge
, the sum of the labels
is not greater than the edge's weight. The bipartite case makes use of the subgraph of equality edges: edges whose reduced weight (weight less the labels at the two ends) is 0. Both the unweighted and weighted bipartite case make use of alternating path trees; the key idea of Edmonds that allowed a general solution was to realize that when odd cycles arose during the tree construction, the cycle (called a
blossom) could be shrunk to a single new vertex (called a
pseudo-node), yielding a smaller derived graph on which the algorithm can be carried forward.
The weighted blossom algorithm uses the following datasets. The original vertex set (of size
) is denoted
and we keep track of the following for the vertices
and edges
of the original graph:
•
, the list of pseudo-nodes that
is absorbed into.
•
, the current pseudo-node for
, the last entry in
.
•
, the vertex matched to
(0 if unmatched).
•
, the current weight of the edge
.
•
Tree edges, a subset of the edges of
; the tree edge
indicates that
is the parent of
.
•
Equality edges: edges
such that
and
.
Let
denote the
derived graph, which consists of all vertices not currently in a blossom, together with all current pseudo-nodes, each of which represents a blossom. We use
for the pseudo-nodes. Then for the derived graph with vertex set
we keep track of the following:
•
, the parent of
in the tree;
if
is not in the tree or is the root.
•
, the label of
. In the Demonstration image the labels shown are the more relevant values
.
•
gives the reduced weight of edge
:
.
A vertex in the tree is called
odd or
even depending on its distance to the root (the root is even). The subset of
consisting of odd (resp., even) vertices is denoted
(
resp.
). And as the matching is constructed (and destroyed, since matching edges inside a blossom are deleted in Case 3), a vertex
is called
matched if there is a vertex
such that
and
.
The algorithm loops through five cases until exiting via Case 1. Start with the initial labeling
and the empty matching.
Case 1: Augment the matching. Do this if there is an equality edge
with
and
being unmatched; the edge
and the path from
to the root in the tree are used to augment the matching. If there is an unmatched vertex
in
, then reset the tree to consist only of such a vertex. Otherwise expand all remaining pseudo-nodes in reverse order and return the final matching.
Case 2: Augment the tree with two new edges. Do this if Case 1 fails and there is an equality edge
with
,
,
not in the tree, and
a matched vertex. Add the edges
and
where
is chosen so that
and
;
is taken to be
.
Case 3: Shrink a blossom and update the tree, weights, and matching. Do this if previous cases fail and there is an equality edge
such that
, and
. Introduce a vertex
for the new pseudo-node that is larger than any previously used, and set
. When a blossom is shrunk, edges within the blossom are ignored: if they were in the matching or tree they are removed and even if they satisfy the equality edge condition, they are not considered equality edges. The weight updating step proceeds by
for each original vertex
lying in the cycle, even hereditarily, and each vertex
not in the cycle.
Case 4: Expand an odd pseudo-node and update the tree, weights, and matching. Do this if previous cases fail and there is a pseudo-node
for which
. Delete
from each list
where
. The weight update proceeds by
for each original vertex
lying, even hereditarily, in the cycle that
represents and each vertex
not in the cycle. This step is also used when the final expansion of blossoms is called upon in Case 1.
Case 5: Update the labels on vertices in
that are in the current tree. Do this if none of the preceding cases hold. Compute
as described in [1] and increase
by
for any
and reduce
by
for any
.
For the finer details of what is done in these cases, the author refers the reader to [1].
The complexity of the algorithm stems from two features: (1) blossoms can become vertices in subsequent blossoms, and (2) in Case 4 we can expand a pseudo-node out of order. Problem (1) requires keeping careful track of the current blossom for a given original vertex, and (2) requires updating many values in the stored data, since the expanded pseudo-node no longer exists.
To understand the output in the Demonstration, keep in mind that trees are represented two ways: the parent structure in
describes the tree, but the edges come from vertices in
such that
is in the tree. Thus, for example, one can have tree edges
and
that are adjacent in the tree because the corresponding derived vertices
and
are the same. Also note that the derived graph is really a multigraph, since if, say,
is 6 and the cycle 4, 5, 6 was just shrunk into the pseudo-node 7, then the edges
,
, and
all exist in the derived graph, even though their ends (4, 5, 6) are all the same vertex in
.
Snapshot 1 [seed 2, 6 vertices, step 12]: The derived graph at step 12 has four vertices (2, 3, 6, and the pseudo-node 7 representing {1, 4, 5}) and there are three equality edges, one of which is in the matching. The next step extends the tree from
to
, which allows the matching to be augmented to
. This is now a perfect matching in the 4-vertex derived graph and the final blossom expansion adds
to get the final minimal-weight matching in the original graph. Note that at the last step the label values are such that each matching edge is an equality edge. By a basic theorem [6, Thm. 5.5] this proves that the matching is minimal.
Snapshot 2 [seed 6, 12 vertices, step 36]: Here the derived graph's vertices are {2, 3, 7, 8, 16}, where 16 represents {1, 4, 5, 6, 9, 10, 11}. The tree is
. The labels have just been changed and
has just become an equality edge that creates a blossom because 1 is part of pseudo-node 16, thus closing the cycle via
. So pseudo-node 17 gets introduced and the derived graph has only the two vertices 12 and 17. The minimal matching there is
with weight 3 and the subsequent expansion of the remaining pseudo-nodes 17, 16, 15, and 14 leads to the final answer. Note that blossom 13 was eliminated earlier, at step 26. And at the final step the matching edges are not contained in the equality edges, though that does always hold true prior to the final expansion of pseudo-nodes.
Snapshot 3 [seed 6, 6 vertices, step 18]: In this example the minimum matching weight is 70 and the largest feasible labeling sum is 67, so a feasible labeling that proves the matching minimal does not exist. Note that the final matching is not a subset of equality edges. In this case there is no feasible labeling for which the equality edges contain the matching.
[1] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver,
Combinatorial Optimization, New York: Wiley, 1998.
[6] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, New York: Elsevier, 1976.
![[Snapshot]](HTMLImages/index.en/thumbnail_1.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_2.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_3.gif)
Embed Interactive Demonstration 
Browse all topics
