3
$\begingroup$

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.

addendum
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.

$\endgroup$
4
  • 1
    $\begingroup$ In what domain are the the weights? Are they all positive or all negative? $\endgroup$
    – joro
    Dec 14, 2015 at 11:48
  • $\begingroup$ @joro the weights are all positive and one may also assume that the triangle inequality holds. $\endgroup$ Dec 14, 2015 at 11:59
  • $\begingroup$ 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. $\endgroup$
    – joro
    Dec 14, 2015 at 13:36
  • $\begingroup$ @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. $\endgroup$ Dec 15, 2015 at 9:02

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Dec 16, 2015 at 4:22
1
$\begingroup$

Partial answer for practical approach.

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

From the above link:

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. 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.

The input is C++ program (check the example) and if necessary the C++ graph/weights can be generated from another language and the output.

As far as I can tell, the Leda headers and libraries are free, but the source code might be paid, check the home page for details.

$\endgroup$
5
  • $\begingroup$ I have already checked Leda, but from the description of the free edition and e.g. the professional edition, it seems that the free edition doesn't include the graph and network algorithms; but I will check again. The LEMON library offers matchng calculations, but installation under Windows is challenging. $\endgroup$ Dec 15, 2015 at 9:34
  • $\begingroup$ @ManfredWeis For windows, you can try running Linux in a virtual machine, it is easy and the performance is near native. Unless you need windows. $\endgroup$
    – joro
    Dec 15, 2015 at 9:46
  • $\begingroup$ thanks for the tip, I will use some of my vacation and try to get the matching problem running. $\endgroup$ Dec 15, 2015 at 10:00
  • $\begingroup$ @ManfredWeis LEMON is a nice library, I'd recommend using it for your MWPM needs ---- there are other codes also out there which work better depending on graph sparsity, but at this stage I think LEMON should be good enough! $\endgroup$
    – Suvrit
    Dec 15, 2015 at 14:52
  • $\begingroup$ @Suvrit looks like LEMON will be my choice; the free version of LEDA seems not to cover MWPM and the fees for the research license are, uh, well beyond my resources. CONCORDE might also be worth a closer look. $\endgroup$ Dec 16, 2015 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.