3
$\begingroup$

I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here.

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.

Thanks in advance

$\endgroup$
  • $\begingroup$ It's unclear to me how much of the algorithm you do understand, so pardon me for asking a possibly stupid question. Are you familiar with bipartite graphs and the equivalence with odd cycle free graphs? Do you see that you can get a perfect matching in an even cycle but not in an odd cycle? $\endgroup$ – Pål GD Sep 23 '18 at 14:06
  • 1
    $\begingroup$ @PålGD I am familiar with bipartite graphs and the fact that there can't be an odd cycle in a bipartite graph. And the algorithm asks for maximum, not necessarily perfect matching. I just couldn't see why odd cycles were a problem. In the question I asked on MSE, I got an answer that says if I have an odd cycle, I can have the path in the cycle as an augmenting path; but I can't reverse the marching in the odd cycle as I will then have one vertex matched to 2 edges. This explanation looks convincing to me. I think this is the problem with odd cycles, isn't it? $\endgroup$ – ab123 Sep 23 '18 at 15:48
  • $\begingroup$ Did you understand it? $\endgroup$ – Manoharsinh Rana Apr 6 at 19:33

Your Answer

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

Browse other questions tagged or ask your own question.