Is there a polynomial algorithm for finding the maximum weighted perfect match in the general graph?

Question

I see that the Blossom algorithm can be used to solve an unweighted version of this problem, and I know that this problem can also be reduced to the LP problem (but with exponential number constraints). Is there a way to solve this in polynomial time?

Answer 1

Yes, the Blossom algorithm for calculating maximum unweighted common matches can be used in the primary-double algorithm for maximum weighted common matches (this is a common method, the Hungarian algorithm is the bipartite equivalent). There was an implementation called Blossom V because of Vladimir Kolmogorov.