0
$\begingroup$

I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must recur to the blossom algorithm.

The explanations that I found (1. here, 2. and here) are based on the fact that the direction that I choose to start exploring an odd loop in the Depth First Search (DFS) could make me miss an augmented path.

But it seems to me that this issue can be solved by considering the same vertex distinct during the DFS if I am entering it through a matched edge or an unmatched one, why isn't this enough?

$\endgroup$
4
  • $\begingroup$ Can you explain with an example how your suggestion helps? If we enter a vertex $v$ first through a matched edge $uv$ and then again through an unmatched one, our next step would be to walk backwards along $vu$, which confuses me and doesn't seem to help find an augmenting path. $\endgroup$ Commented Feb 8, 2021 at 0:41
  • $\begingroup$ You still don't loop in a single path from the root, but when you start a new branch you explore also nodes that were seen in previous paths if you are entering them with a different type of edge (matched or unmatched) $\endgroup$
    – Claudio P
    Commented Feb 8, 2021 at 9:05
  • $\begingroup$ An immediate drawback I see is that you might end up finding a path which contains the same edge twice (once in each direction) which is not an augmenting path. But the obvious answer to that is "modify DFS so that, in addition, you're not allowed to reuse an edge" and I don't see right away what goes wrong if you do that. $\endgroup$ Commented Feb 8, 2021 at 18:03
  • $\begingroup$ You cannot use the same edge twice if you avoid loops. $\endgroup$
    – Claudio P
    Commented Feb 8, 2021 at 18:11

1 Answer 1

0
$\begingroup$

I posted the question on the computer science sub as well (is that legal?) and ending finding the solution at the end: https://cs.stackexchange.com/questions/135278/maximum-matching-for-general-graph/135336#135336

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .