Blossom V

This Blossom V software implements an algorithm that solves the following problem:

Given an undirected weighted graph, it computes a perfect matching of minimum cost.

The implemented algorithm is described in the following paper:

Vladimir Kolmogorov.

“Blossom V: A new implementation of a minimum cost perfect matching algorithm”

Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.

On many types of problems Blossom V outperforms previous implementations of Cook and Rohe (“Blossom IV”) and of Mehlhorn and Schaefer, sometimes by an order of magnitude. The key feature of Blossom V that gives this improvement is a combination of two ideas that previously were used only separately: (i) a flexible dual update strategy and (ii) a use of priority queues.

The software assumes that the graph contains at least one perfect matching; if it is not the case then the behaviour is undefined. The code can also be used for computing a maximum (non-perfect) matching: the latter problem can be reduced to a perfect matching problem via a reduction described in section 1.5.1 of Guido Schäfer's Master's thesis “Weighted matchings in general graphs”. This reduction doubles the size of the graph.

By default, the code uses weights of type “int”. While it is possible to change it to “double”, it is not recommended: rounding errors may then lead to unexpected behaviour, such as non-termination. Internally, small numbers are represented as differences of big numbers, so with a floating point precision the code becomes unstable.