Generalization of the Hungarian algorithm to general undirected graphs?

Question

The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important primal-dual method. The algorithm was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian algorithm" because the algorithm was based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. Munkres reviewed the algorithm in 1957 and observed that it is indeed polytime. Since then the algorithm is also known as Kuhn-Munkres algorithm.

Although the Hungarian contains the basic idea of the primal-dual method, it solves the maximum weight bipartite matching problem directly without using any linear programming (LP) machinery. Thus, in answer of the following question, Jukka Suomela commented

Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance. [...] You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.

In other words, you don't have to worry about how to round a rational/floating point solution from the LP solver to get back a maximum weight perfect matching of a given bipartite graph.

My question is the following:

Is there a generalization of the Hungarian algorithm that works for general undirected graph without the use of LP machinery similarly to the spirit of the original Hungarian algorithm?

I would prefer modern and easy-to-read exposition instead of some original complicated paper. But any pointer will be very appreciated!

Many thanks in advance and Merry Christmas!!!

---

Update: The question is nicely answered by Arman below. I just want to point out that another nice source to study the Edmonds's Blossom Algorithm (for the weighted case) is Chapter 11 of Combinatorial Optimization by Korte and Vygen. Google book actually shows nearly all the parts I need to understand the algorithm.

Answer 1

Edmonds's matching algorithm (also called Blossom Algorithm) solves the maximum matching on general graphs. Actually it is a generalization of alternating paths method. (I am not sure of the name of the method but it shoud be König-Hall method.) It basically finds augmenting paths (see wikipedia page: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm) to extend the current matching and stops if there is no more augmenting paths. In general graphs, the only problem occurs in odd cycles. In the Edmonds's matching algorithm odd cycles are contracted (blossoms) and expended back to have a solution.

There is also a correspondence between Blossom Algorithm and Primal Dual method. Odd cycles cause fractional extreme points. Therefore we add so called blossom inequalities for each odd cycle.

Minimum weighted perfect matching and maximum weight matching problems could also be handled with this approach.

For details of the algorithm, see http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

For mathematical formulation and the corresponding primal-dual method, see http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf

Answer 2

Two years ago, when researching the (unweighted) blossom algorithm, I found two great sets of notes, one by Tarjan and one by Zwick. They made the unweighted case seem quite straightforward and I was able to implement it in Mathematica using recursion. It works quite well.

The notes that I found useful are

http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf and http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf

They distill it all down to very simple terms that allow one to think recursively and then, as noted, program recursively.

I think it should all work in the weighted case, which I trying to get implemented now.