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.