4
$\begingroup$

Edmond's blossom algorithm computes a maximum weight matching in a general graph (https://en.wikipedia.org/wiki/Blossom_algorithm). Many papers also reference to Edmond's blossom algorithm to compute a Maximum weight perfect matching. I don't understand how this is possible. Given for instance the following graph (a square with one diagonal):

V={0,1,2,3}, E={(0,1),(1,2),(2,3),(3,0),(0,2)}. All edges have weight one, except the diagonal edge (0,2) which has weight 10.

A maximum weight perfect matching would be M1={(0,1),(2,3)} with weight 2. However a maximum weight (non-perfect) matching in the same graph would be M2={(0,2)} with weight 10. So how can the same algorithm be used to compute a perfect matching?

See for instance the introduction in the following papers:

  1. Kolmogorov Blossom, V: a new implementation of a minimum cost perfect matching algorithm

  2. Cook, Rohe, Computing Minimum-Weight Perfect Matchings

$\endgroup$

2 Answers 2

7
$\begingroup$

Suppose you have a graph with edge weights $w_e$. Add constant $M > \sum_e |w_e|$ to all the weights, obtaining $w'_e = M + w_e$. If there is a perfect matching, its (primed) weight is greater than the (primed) weight of any non-perfect matching. Thus the matching of maximum (primed) weight is a maximum-weight perfect matching.

$\endgroup$
4
  • $\begingroup$ This doesn't seem to be correct. Here's a counter example (cycle graph with 2 extra edges). V={0,1,2,3,4,5} E={(0,1),(1,2),(2,3),(3,4),(4,5),(5,0), (1,3),(0,4)}. All edges have weight 1, except edges (1,3),(0,4) which have weight 10. Set M=11. Then all edges have weight 11, except edges (1,3),(0,4) which have weight 21. A maximum weight perfect matching would be M1={(0,1),(2,3),(4,5)} with weight 33. However, the non-perfect matching M2={(1,3),(0,4)} has weight 42. Could you confirm this? $\endgroup$ Commented Mar 29, 2017 at 14:21
  • $\begingroup$ Oops, meant sum rather than max. Editing. $\endgroup$ Commented Mar 29, 2017 at 16:53
  • $\begingroup$ Yes that seems to work. Is this a known transformation (reference?), or did you come up with this? $\endgroup$ Commented Mar 29, 2017 at 17:25
  • 1
    $\begingroup$ A well-known strategy to enforce a constraint is to add an appropriate term to the objective. $\endgroup$ Commented Mar 29, 2017 at 18:41
0
$\begingroup$

Presumably if all the weights are equal, the the maximum matching is a perfect matching, so that weighting can be used to find a perfect matching if there is one. All the references I can find use the Edmonds algorithm to find the maximum matching, not necessarily perfect.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .