Maximum matching for general graph

Question

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? To be more precise, what I mean is that during a DFS, you still avoid loops, so you stop if you enter a node that is already in the path between the root and the current node, but you still explore nodes that you have visited in previous paths if you are entering them from a different type of edge (matched or not matched).

Answer 1

I think the issue will be that, if we allow each vertex to be considered twice (once per incoming edge type), then we need some way to remember that if we have already visited one "flavour" of a vertex on the path from the BFS root so far, we must avoid visiting its other flavour further along the same path (since such a path would no longer be simple). This seems to entail keeping track of all, or at least all minimal (w.r.t. set inclusion) sets of vertices used on the path to each vertex considered in the BFS so far, which in the worst case would multiply time (and possibly space) requirements by a factor exponential in $|V|$.

Why is it not necessary to explicitly keep track of which vertices have been used in the usual Hopcroft-Karp algorithm for maximum matching in bipartite graphs, which considers each vertex only once? Because the BFS step used in that algorithm to find augmenting paths automatically ensures that all paths from the BFS root are shortest paths, and thus that they are all simple.

Answer 2

I found the answer myself at the end.

Consider this graph and matching (full edge are matched and dashed are not) and suppose we start by exploring the red path from node 1 to 9: we cannot continue since entering node 7 would create a loop, but during this path we marked node 8 as visited from a non matched edge, and so we will not enter node 8 again through a not matched edge and we will miss the following augmenting path: .

I think that this one is the minimum graph in terms of number of nodes that fails for the algorithm, so it is actually not trivial to understand that the algorithm is flawed