Is there a polynomial algorithm to find the max weighted perfect matching in a general graph?

Question

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

Answer 1

Yes, the Blossom algorithm for computing maximum unweighted general matchings can be used in a primal-dual algorithm for maximum weighted general matchings (this is a general technique; the Hungarian algorithm is the bipartite equivalent). There's an implementation called Blossom V due to Vladimir Kolmogorov.