1
$\begingroup$

Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph algorithm to construct a maximum matching in a graph (matching is a set of edges without any common vertex; maximum matching is a matching with the highest cardinality of this set).

I do understand the idea behind finding augmenting paths and reversing the matching on them to get a matching with one higher cardinality,

what I don't understand is why odd cycles are a problem in finding an augmenting path (the algorithm says to "shrink" any odd cycle found while searching for an augmenting path).

My best guess is that an odd cycle doesn't allow you to visit some path connected to the cycle because you come back along the same path that led you to the cycle? but I am not sure.

How does an odd cycle create a problem, but even cycle doesn't?

A simple visual description, if someone can provide, might also be helpful.

Also, is this question suitable for this site or should I ask it on CS stackexchange instead?

$\endgroup$
1
$\begingroup$

When looking for an augmenting path $P$, we are looking for a set of edges which we can with some edges in the current matching $M$ to hopefully obtain some bigger matching $M'$. In particular, along an alternating path $P$ the edges alternate between being in $M$ and being in $M'$. Now suppose this augmenting path $P$ is in fact an odd cycle. By definition a matching cannot contain two adjacent edges. However, note that since $P$ is an odd cycle and the edges along $P$ alternate between being in $M$ and being in $M'$, then $P$ must contain two adjacent edges from $M$ or two adjacent edges from $M$ (draw out some examples to see this). Thus we cannot swap edges on an augmenting path which is an odd cycle to obtain a bigger matching, and so instead we keep the edges in $M$ which are in this odd cycle. In other words, we are not interested in the odd cycle augmenting paths since we cannot obtain a bigger matching from them.

$\endgroup$
  • $\begingroup$ Oh, I get it now. But couldn't we just check that if the vertex at the end of the augmenting path is not same as the starting vertex, then don't consider that alternating path as an augmenting path, and continue searching other paths? $\endgroup$ – ab123 Sep 23 '18 at 8:16
  • $\begingroup$ I think shrinking an odd cycle does exactly the same thing as ignoring an odd cycle? $\endgroup$ – ab123 Sep 23 '18 at 8:24
  • $\begingroup$ It does indeed correspond to ignoring the cycle. In response to your first question, the problem with your suggestion is that the method used by Edmond's algorithm to efficiently find augmenting paths doesn't necessarily notice if we "see" the same vertex twice - it essentially works by considering pairs of M edges and non-M edges as single edges in some special auxiliary graph G whose paths form alternating paths in the original bipartite graph ( try drawing some examples out for yourself). Hope this helps. $\endgroup$ – JRyan Sep 23 '18 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.