Algorithmic Solutions > LEDA > 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

Computing weighted perfect matchings in a graph is very complicated. Checking the result is much easier. Moreover, checking is only linear in the size of the graph. So, the overhead is quite small. We recommend to use the internal checking functions to ensure the correctness of the result.

Matching Algorithms

Maximum Weighted Matching in General Graphs

Bipartite Weighted Assignment

Bipartite Maximum Weighted Maximum Cardinality Matching

Maximum Cardinality Matching in Bipartite Graphs

Graphs and Related Data Types

Graph Algorithms

Manual Entries:

Manual Page General Weighted Matching