LEDA Guide: Weighted Perfect Matching in General Graphs

> LEDA Guide > Graph Algorithms > Matching Algorithms > Weighted Perfect Matching in General Graphs

Weighted Perfect Matching in General Graphs

What is a Weighted Perfect Matching?

A matching in a graph G=(V,E) is a subset M of the edges E such that no two edges in M share a common end node. A perfect matching M in G is a matching such that each node of G is incident to an edge in M. If the edges of the graph have an associated weight, then a maximum (minimum) weighted perfect matching is a perfect matching such that the sum of the weights of the edges in the matching is maximum (minimum).

We use the term general graph to indicate that the graph is not bipartite. Matchings in bipartite graphs can be computed more efficiently than matchings in general (=non-bipartite) graphs.

Intuition Maximum Weighted Perfect Matching: Suppose we have a set of workers. These are the nodes in our graph. We want to build pairs of workers that work together. For each pair of workers we know the profit we get if the two work together. This defines the weights of the edges of the graph. In the maximum weighted perfect matching problem we want to find pairs of workers such that all workers have a mate and the total profit is maximum.

Edge Weight Restrictions

The algorithms for weighted perfect matching in general graphs use divisions. So, in order to avoid rounding errors for the number type int, please make sure that all edge weights are multiplicatives of four. Note that the algorithm will automatically multiply all edge weights by four if this condition is not met. Remark: Multiplying all edge weights by a constant factor f does not change the weighted perfect matchings of a graph. Only the weight of each matching is f times bigger.

LEDA Functions for Weighted Perfect Matching

MAX_WEIGHT_PERFECT_MATCHING() computes a maximum weighted perfect matching in a general graph. By default the result of the computation is checked internally. This check can be disabled. There is also an explicit check function available. However, using this explicit check functions is quite complicated.

MIN_WEIGHT_PERFECT_MATCHING() computes a minimum weighted perfect matching in a general graph. By default the result of the computation is checked internally. This check can be disabled. There is also an explicit check function available. However, using this explicit check functions is quite complicated.

Example of MIN_WEIGHT_PERFECT_MATCHING and MAX_WEIGHT_PERFECT_MATCHING()

Running times

For a graph G=(V,E), the running times of computing weighted perfect matchings is O(|V|*|E|log|V|)). The checking functions are linear in the size of the graph.

Tips