Maximum Weighted Matching

template <typename Graph, typename MateMap>
void maximum_weighted_matching(const Graph& g, MateMap mate);

template <typename Graph, typename MateMap, typename VertexIndexMap>
void maximum_weighted_matching(const Graph& g, MateMap mate, VertexIndexMap vm);

template <typename Graph, typename MateMap, typename VertexIndexMap, typename EdgeWeightMap>
void maximum_weighted_matching(const Graph& g, MateMap mate, VertexIndexMap vm, EdgeWeightMap weights);

template <typename Graph, typename MateMap>
void brute_force_maximum_weighted_matching(const Graph& g, MateMap mate);

template <typename Graph, typename MateMap, typename VertexIndexMap>
void brute_force_maximum_weighted_matching(const Graph& g, MateMap mate, VertexIndexMap vm);

Before you continue, it is recommended to read about maximal cardinality matching first. A maximum weighted matching of an edge-weighted graph is a matching for which the sum of the weights of the edges is maximum. Two different matchings (edges in the matching are colored blue) in the same graph are illustrated below. The matching on the left is a maximum cardinality matching of size 8 and a maximal weighted matching of weight sum 30, meaning that is has maximum size over all matchings in the graph and its weight sum can't be increased by adding edges. The matching on the right is a maximum weighted matching of size 7 and weight sum 38, meaning that it has maximum weight sum over all matchings in the graph.

Both maximum_weighted_matching and brute_force_maximum_weighted_matching find a maximum weighted matching in any undirected graph. The matching is returned in a MateMap, which is a ReadWritePropertyMap that maps vertices to vertices. In the mapping returned, each vertex is either mapped to the vertex it's matched to, or to graph_traits<Graph>::null_vertex() if it doesn't participate in the matching.

Algorithm Description

The maximum weighted matching problem was solved by Edmonds in [74]. Subsequently, Gabow [75] and Lawler [20] developed methods to reduce the run time from O(V⁴) to O(V³). The implementation of maximum_weighted_matching follows a description of the O(V³) algorithm by Galil [77].

Starting from an empty matching, the algorithm repeatedly augments the matching until no further improvement is possible. Alternating trees and blossoms are used to find an augmenting path, in a way that is similar to maximum cardinality matching. A linear programming technique is used to ensure that the selected augmenting path has maximum weight. This involves assigning dual variables to vertices and blossoms, and computing slack values for edges.

The outline of the algorithm is as follows:

0. Start with an empty matching and initialize dual variables to half of the maximum edge weight.
1. (Labeling) Root a tree at each non-matched vertex, and proceed to construct alternating trees by labeling, using only edges with zero slack value. If an augmenting path is found, go to step 2. If a blossom is formed, go to step 3. Otherwise, go to step 4.
2. (Augmentation) Find the augmenting path, tracing the path through shrunken blossoms. Augment the matching. Deconstruct and unlabel the alternating trees traversed by the augmenting path. Go to step 1.
3. (Blossoming) Identify the blossoms in the alternating cycle and shrink these into a newly formed blossom. Return to step 1.
4. (Updating dual variables) Adjust the dual variables based on the primal-dual method. If this enables further growth of the alternating trees, return to step 1. Otherwise, halt the algorithm; the matching has maximum weight.

The implementation deviates from the description in [77] on a few points:

• After augmenting the matching, [77] expands all blossoms with zero dual. This is correct but potentially unnecessary; some of the expanded blossoms will be recreated during the next stage. The implementation holds off on the expansion of such blossoms. In any scenario where a blossom must be expanded to make progress, label T will be assigned to it. At that point, the blossom will be expanded through a zero-delta dual step. The additional cost is O(V) per expanded blossom, and the total number of blossom expansions is O(V²), therefore this does not change the overall time complexity of the algorithm.
• The algorithm records a minimum-slack edge e_k,l for every pair of blossoms B_k, B_l. Storing these edges in a 2-dimensional array would increase the space complexity to O(V²); an unfortunate cost for large sparse graphs. The implementation of maximum_weighted_matching avoids this by maintaining, for each blossom B_k, a list B_k.best_edge_set that contains the non-empty elements of e_k,l, plus edges between B_k and B_l discovered after shrinking B_k. The combined length of these lists is O(E), since any edge is contained in at most two lists. The algorithm only ever examines e_k,l during the process of merging B_k into a larger blossom. In that case, it sequentially examines e_k,l for all l, taking time O(V). The implementation handles this by examining every element of B_k.best_edge_set, taking time O(V) plus a constant time per newly discovered edge. This does not change the overall time complexity of the algorithm.
• After augmenting, [77] removes all labels and alternating trees. This keeps the algorithm simple, but it causes many trees and labels to be rediscovered at the beginning of the new stage. To avoid such redundent work, maximum_weighted_matching removes labels only from the two alternating trees that are touched by the augmenting path. All other labels and trees are reused in the next stage. Erasing labels from a subset of the graph, requires updating the data structures that track minimum-slack edges. This involves examining all edges that either touch a blossom which loses its label or touch a vertex which depended on a lost label. These steps take O(V + E) per stage, adding up to O(V³) in total. Although this strategy does not improve the worst-case time complexity of the algorithm, it achieves a significant speedup in benchmarks on random graphs.

If edge weights are integers, the algorithm uses only integer computations. This is achieved by internally multiplying edge weights by 2, which ensures that all dual variables are also integers.

A brute-force implementation brute_force_maximum_weighted_matching is also provided. This algorithm simply searches all possible matchings and selects one with the maximum weight sum.

Where Defined

boost/graph/maximum_weighted_matching.hpp

Parameters

An undirected graph. The graph type must be a model of Vertex and Edge List Graph and Incidence Graph. The graph may not contain parallel edges.

Must be a model of ReadablePropertyMap, mapping vertices to integer indices in the range [0, num_vertices(g)). If this parameter is not explicitly specified, it is obtained from the internal vertex property of the graph by calling get(vertex_index, g).

Must be a model of ReadablePropertyMap, mapping edges to weights. Edge weights must be integers or floating point values. If this parameter is not explicitly specified, it is obtained from the internal edge property of the graph by calling get(edge_weight, g).

Must be a model of ReadWritePropertyMap, mapping vertices to vertices. For any vertex v in the graph, get(mate,v) will be the vertex that v is matched to, or graph_traits::null_vertex() if v isn't matched.

Complexity

Let m and n be the number of edges and vertices in the input graph, respectively. Assuming the VertexIndexMap and EdgeWeightMap both provide constant-time lookup, the time complexity for maximum_weighted_matching is O(n³). For brute_force_maximum_weighted_matching, the time complexity is exponential in m.

Note that the best known time complexity for maximum weighted matching in general graph is O(nm+n²log(n)) by [76], but relies on an efficient algorithm for solving nearest ancestor problem on trees, which is not provided in Boost C++ libraries.

Example

The file example/weighted_matching_example.cpp contains an example.