LEDA Guide: Bipartite Maximum Weighted Maximum Cardinality Matching

> LEDA Guide > Graph Algorithms > Matching Algorithms > Bipartite Maximum Weighted Maximum Cardinality Matching

Bipartite Maximum Weighted Maximum Cardinality Matching

What is a Maximum Weighted Maximum Cardinality Matching in a Bipartite Graph?

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 maximum cardinality matching is a matching with a maximum number of edges. If the edges of the graph have an associated weight, then a maximum weighted matching is a matching such that the sum of the weights of the edges in the matching is maximum. A maximum weighted maximum cardinality matching is a maximum cardinality matching with maximum weight.

A graph is bipartite if it has two kinds of nodes and the edges are only allowed between nodes of different kind. A matching in a bipartite graph therefore assigns nodes of one kind to nodes of the other kind. Matchings in bipartite graphs can be computed more efficiently than matchings in general (=non-bipartite) graphs.

Intuition: Suppose we have a set of workers and a set of machines. These are the two kinds of nodes in our bipartite graph. We know which worker can handle which machines. This defines the edges of the bipartite graph. Additionally, we know the profit of assigning worker w to machine m. This defines the edge weight. Our task in the maximum weighted maximum cardinality matching problem is to assign a maximum number of workers to machines in such a way that the profit is maximum.

Proof of Optimality of the Resulting Matching

All functions for computing weighted matchings in bipartite graphs provide a proof of optimality in the form of a potential function pot for the nodes of the graph. The potential function corresponds to the node cover in Maximum Cardinality Matching in Bipartite Graphs. Details can be found in the LEDA Book.

The Number Type for the Edge Weights

The function for computing a bipartite maximum weighted maximum cardinality matching is a template function. The template parameter NT can be instantiated with any number type. Additionally, there are preinstantiated versions for int and double. The names of the template functions have suffix _T and the functions without suffix _T are the preinstantiated versions

The reason why we did not restrict our algorithms to int and double is that the number types int, float, and double provided by C++ are only crude approximations of the mathematical counterparts: ints can overflow, the arithmetic for floats and doubles incurs rounding errors. The functions in this section only perform correctly if all arithmetic is performed without rounding errors.

LEDA Function for Bipartite Maximum Weighted Maximum Cardinality Matching

MWMCB_MATCHING_T() computes a maximum weighted maximum cardinality matching in a bipartite graph. MWMCB_T() is a template function. The template parameter NT can be instantiated with any number type.

Example of MWMCB_MATCHING_MATCHING_T()

MWMCB_MATCHING() is the name of the preinstantiated versions of MWMCB_T(). There is one function for edge weights of type int and one for double.

Important Notice: MWMCB() only performs correctly if all arithmetic is performed without rounding errors and without overflows. If you are not sure about this, you should use MWMCB_T() with one of the LEDA number types.

Example of MWMCB_MATCHING()

Running times

For a bipartite graph G=(V,E), the running times of of computing a maximum weighted maximum cardinality matching is O(|V|*(|E|+|V|log|V|)).

Tips

Use MWMCB_T() to compute a maximum weighted maximum cardinality matching in a bipartite graph.
If you are determined to use MWMCB()be aware of the arithmetic problems that may arise.