title: Is there a polynomial algorithm to find the max weighted perfect matching in a general graph?
body: <p>I see that <a href="https://en.wikipedia.org/wiki/Blossom_algorithm" rel="noreferrer">Blossom algorithm</a> 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?</p>