JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums TopCoder Cookbook Algorithm Competitions - New Recipes Re: Solving Maximum Bipartite Matching Problem Revision History (3 edits)
Re: Solving Maximum Bipartite Matching Problem (response to post by ibra)
Hello all,

I've been studying this topic lately, and I came out with a question which answer I have not been able to figure out.

First of all, this question is actually about matching in general graphs, not bipartite graphs. It turns out that the algorithm for solving this problem is very similar to "Kuhn's algorithm" but when it finds an odd-length cycle it shrinks it into a single node and continues the search. The algorithm is called "Edmonds' Blossom algorithm".

However, it is well known that a given matching is the maximum one if and only if no more augmenting paths can be found on the graph. So, my question is the following one:

Kuhn's algorithm simply finds an augmenting path in the graph for including new matched edges. Therefore in principle it should also work for general graphs: if no more augmenting paths are found, then necessarily we have a maximum matching!. So I implemented the algorithm adding some extra information in the DFS for avoiding cycles and tested it for bipartite graphs and worked perfectly, however when it comes to general graphs it fails... of course the reason is because there are augmenting paths the algorithm cannot find (apparently because of odd-length cycles, a.k.a. blossoms), but why?

All of this converges to a simple question: why in Edmonds' algorithm is it necessary to shrink blossoms? I've read many papers where it is explained how to shrink blossoms and why an augmenting path in the reduced graph is still valid in the expanded one, but they never explain why this is actually necessary!

Thanks for your help.
Re: Solving Maximum Bipartite Matching Problem (response to post by ibra)
Hello all,

I've been studying this topic lately, and I came out with a question which answer I have not been able to figure out.

First of all, this question is actually about matching in general graphs, not bipartite graphs. It turns out that the algorithm for solving this problem is very similar to "Kuhn's algorithm" but when it finds an odd-length cycle it shrinks it into a single node and continues the search. The algorithm is called "Edmonds' Blossom algorithm".

However, it is well known that a given matching is the maximum one if and only if no more augmenting paths can be found on the graph. So, my question is the following one:

Kuhn's algorithm simply finds an augmenting path in the graphs for including new matched edges. Therefore in principle it should also work for general graphs: if no more augmenting paths are found, then necessarily we have a maximum matching!. So I implemented the algorithm adding some extra information in the DFS for avoiding cycles and tested it for bipartite graphs and worked perfectly, however when it comes to general graphs it fails... of course the reason is because there are augmenting paths the algorithm cannot find (apparently because of odd-length cycles, a.k.a. blossoms), but why?

All of this converges to a simple question: why in Edmonds' algorithm is it necessary to shrink blossoms? I've read many papers where it is explained how to shrink blossoms and why an augmenting path in the reduced graph is still valid in the expanded one, but they never explain why this is actually necessary!

Thanks for your help.
Re: Solving Maximum Bipartite Matching Problem (response to post by ibra)
Hello all,

I've been studying this topic lately, and I came out with a question which answer I have not been able to figure out.

First of all, this question is actually about matching in general graphs, not bipartite graphs. It turns out that the algorithm for solving this problem is very similar to "Kuhn's algorithm" but when it finds an odd-numbered cycle it shrinks it into a single node and continues the search. The algorithm is called "Edmonds' Blossom algorithm".

However, it is well known that a given matching is the maximum one if and only if no more augmenting paths can be found on the graph. So, my question is the following one:

Kuhn's algorithm simply finds an augmenting path in the graphs for including new matched edges. Therefore in principle it should also work for general graphs: if no more augmenting paths are found, then necessarily we have a maximum matching!. So I implemented the algorithm adding some extra information in the DFS for avoiding cycles and tested it for bipartite graphs and worked perfectly, however when it comes to general graphs it fails... of course the reason is because there are augmenting paths the algorithm cannot find (apparently because of odd-length cycles, a.k.a. blossoms), but why?

All of this converges to a simple question: why in Edmonds' algorithm is it necessary to shrink blossoms? I've read many papers where it is explained how to shrink blossoms and why an augmenting path in the reduced graph is still valid in the expanded one, but they never explain why this is actually necessary!

Thanks for your help.
Re: Solving Maximum Bipartite Matching Problem (response to post by ibra)
Hello all,

I've been studying this topic lately, and I came out with a question which answer I have not been able to find anywhere.

First of all, this question is actually about matching in general graphs, not bipartite graphs. It turns out that the algorithm for solving this problem is very similar to "Kuhn's algorithm" but when it finds an odd-numbered cycle it shrinks it into a single node and continues the search. The algorithm is called "Edmonds' Blossom algorithm".

However, it is well known that a given matching is the maximum one if and only if no more augmenting paths can be found on the graph. So, my question is the following one:

Kuhn's algorithm simply finds an augmenting path in the graphs for including new matched edges. Therefore in principle it should also work for general graphs: if no more augmenting paths are found, then necessarily we have a maximum matching!. So I implemented the algorithm adding some extra information in the DFS for avoiding cycles and tested it for bipartite graphs and worked perfectly, however when it comes to general graphs it fails... of course the reason is because there are augmenting paths the algorithm cannot find (apparently because of odd-length cycles, a.k.a. blossoms), but why?

All of this converges to a simple question: why in Edmonds' algorithm is it necessary to shrink blossoms? I've read many papers where it is explained how to shrink blossoms and why an augmenting path in the reduced graph is still valid in the expanded one, but they never explain why this is actually necessary!

Thanks for your help.