Details

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.

References

[1] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, Combinatorial Optimization, New York: Wiley, 1998.

[2] M. Kusner and S. Wagon, "The Blossom Algorithm for Maximum Matching", Wolfram Demonstrations Project, 2011.

[3] Egerváry Research Group on Combinatorial Optimization. Lemon Graph Library. (2010) lemon.cs.elte.hu/trac/lemon.

[4] S. Wagon, "The Hungarian Maximum Matching Algorithm," Wolfram Demonstrations Project, 2010.

[5] Wikipedia. "Edmonds's Matching Algorithm." (Dec 13, 2011) en.wikipedia.org/wiki/Edmonds's_matching _algorithm.

[6] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, New York: Elsevier, 1976.