# Bellman-Ford for Matching Problems?

I am looking for a simple way of calculating minimum-weight perfect matchings in complete graphs with an even number of vertices.
I know that there are implementations that are based on Edmond's celebrated Blossom algorithm available, but they come with some installation over/head/aches I currently don't want to invest.

So, I was wondering, if the Bellman-Ford algorithm couldn't be tweaked to find such optimal matchings.
Surely others may have had the same or a similar idea prior to the publication of Edmond's Blossom algorithm, but had to learn that that doesn't work.

Now I would like to know what the obstructions against using Bellman-Ford for matching problems are; any pointers to articles or counter examples will be highly appreciated.

An idea for preventing odd negative cycles
from the answer of user36212 I conclude that the appearing of odd negative cycles is the reason why the "ordinary" Bellman-Ford algorithm can fail to report a minimum-weight perfect matching.
Now my idea to rule out negative odd cycles would be to tweak the edge weights prior to applying the Bellman-Ford algorithm to solve the matching problem as described in the addendum.
The tweak would be to incorporate edge-counting into shortest-path calculations, which can be done e.g. by adding to each edge-weight a sufficiently large value that is the same for each edge; the effect would be, that a cycle containing $m$ matching edges and $k$ non-matching edges will have non-negative length, whenever $k\ge m$.
If $k=m$ then the added constants are canceled out and it depends only on the original edge weights, whether the sum is negative or not; if the sum is negative, the weight of the matching can be improved by exchanging the roles of the edges on the cycle.

the way I would use the Bellman-Ford algorithm would be to start with an arbitrary perfect matching and then, repeat to negate the weights of the matching-edges, check for negative cycles, exchange on such negative cycles the matching-edges with the non-matching edges, until no more negative cycles are detected.
The question is now, what can go wrong with such an algorithm, whether negative cycles with an odd number of vertices could be reported and/or the running time could be exponential.

• In what domain are the the weights? Are they all positive or all negative? – joro Dec 14 '15 at 11:48
• @joro the weights are all positive and one may also assume that the triangle inequality holds. – Manfred Weis Dec 14 '15 at 11:59
• If you are interested for practical solution, there are C++ implementations which solve this efficiently. You can generate the C++ graph and weights from other language, compile, run and parse the output. – joro Dec 14 '15 at 13:36
• @joro a C++ implementation that can be directly integrated into a Visual Studio project would help me for my actual motivation for using matchings, namely checking the quality of TSP heuristics that are based on optimal matchings. But beyond that I am still interested in knowing the reason whether negative cycle detection of the Bellman-Ford algorithm could be exploited to successively improve the quality of matching until finally the optimal solution is found. – Manfred Weis Dec 15 '15 at 9:02

This is something like the first step to Edmonds' algorithm.

You certainly need to insist your cycles should be doing something like alternating, otherwise you cannot use this algorithm at all: it won't preserve a matching. Now, in practice to find negative weight alternating cycles, you need to start searching somewhere (this is what Bellman-Ford does) and you will find a problem combinatorially that what you can actually detect is negative weight alternating even circuits, so that the swapping does not work (you have to search two steps at a time to stay alternating, but then Bellman-Ford may give you circuits).

Now the odd cycles you get like this are nothing other than blossoms, you realise that you can get somewhere by contracting them, and you have Edmonds' algorithm.

For concrete counterexamples, assume all your weights are 0 or 1, so that a minimum weight perfect matching is a maximum matching in the weight 0 edges, and the usual examples which show simple searches don't work apply.

Maybe the simplest counterexample to simple searches for maximum matching consists of three triangles plus a vertex sending one edge to each triangle. Here you should find your algorithm doesn't correctly terminate (it will find a maximum matching, but to certify this it should try to augment and detect impossibility; when it tries to augment it either creates something which is not a matching, or gets stuck cycling between two maximum matchings, depending on how you implement it). By contrast, the blossom algorithm, once it has a maximum matching, will sequentially detect the three triangles as blossoms, contract them, and then the remaining graph doesn't have any augmenting walk, so it stops with a certificate - it's this contraction of blossoms that is key, what is basically going on is that simple search can be confused by a blossom, which it 'should' treat as a single vertex but doesn't, while contracting it removes the possibility for confusion.

There are other, faster, maximum matching algorithms, such as Micali-Vazirani, but then you have much more work in implementation (and these are still essentially blossom algorithms).

• thanks for the nice counter examples; from your explanation I conclude that the appearance of odd cycles is the central issue that could lead to the failure of the Bellman-Ford algorithm. If that is actually the case, then I might have a solution for it. – Manfred Weis Dec 16 '15 at 4:22

The CAS Leda can compute it, consider checking the references.