0
$\begingroup$

I'm trying to learn Edmond's Blossom algorithm for finding a maximum matching in a general graph.

According to Wikipedia:

Given $G = (V, E)$ and a matching $M$ of $G$, a blossom $B$ is a cycle in $G$ consisting of $2k + 1$ edges of which exactly $k$ belong to $M$, and where one of the vertices $v$ of the cycle (the base) is such that there exists an alternating path of even length (the stem) from $v$ to an exposed vertex $w$.

Then it says that in order to find a blossom, you search the graph marking even-level nodes as "outer" and odd-level nodes as "inner", and:

If we end up with two adjacent vertices labeled as outer "o" then we have an odd-length cycle and hence a blossom.

I don't understand why we only consider outer (even-level) nodes. In a graph with edges $(1, 2), (2, 3), (3, 4), (3, 5), (4, 5)$, with the matching $(2, 3), (4, 5)$, node 1 is on level 0, node 2 is on level 1, node 3 is on level 2, nodes 4 and 5 are on level 3. It seems to me like the cycle (3, 4, 5) respects the definition for an odd alternating cycle, yet the algorithm will not consider it because 4 and 5 are on an odd level.

I thought it might be a wikipedia issue, but I've seen a couple of implementations, including a paper from a course at Standford, and they all consider only even-level nodes. What am I missing?

Later edit: to further illustrate my point, in the two graphs in the image below, both $(3, 4, 5)$ (in the left graph) and $(3, 4, 5, 6, 7)$ (in the right graph), are odd alternating cycles. However, the horizontal edge $(4, 5)$ is on a different parity level than the horizontal edge $(6, 7)$. Therefore, no matter how you look at it, one of them should not be considered a cycle during the algorithm, right? Which does not make much sense.

enter image description here

$\endgroup$
0
$\begingroup$

The even/odd level, or equivalently the labeling of vertice as "inner" or "outer", is done with respect to the forest $F$ consisting of the portion of the graph we've already explored. In your example, before we've discovered edge $35$, $F$ will consist of the path from $1$ to $5$, so vertices $3$ and $5$ will both be at even levels: $2$ and $4$. Therefore, edge $35$ connects two vertices at even levels, and so the cycle $(3,4,5)$ is correctly reported as a blossom.

In more detail, here is what will happen:

  1. We start out with $F$ consisting only of vertex $1$. Edges $23$ and $45$ are marked.
  2. Vertex $1$ is an outer vertex of $F$, and there is an unmarked edge $12$. It goes to a vertex $2$ outside $F$, which is matched to $3$. We add all this to $F$; $F$ now has vertices $1,2,3$ and edges $12,23$. We mark the edge $12$.
  3. Vertex $1$ is an outer vertex of $F$, and there are no unmarked edges out of it, so we mark vertex $1$.
  4. Vertex $3$ is an outer vertex of $F$, and there is an unmarked edge $34$. It goes to a vertex $4$ outside $F$, which is matched to $5$. We add all this to $F$; $F$ now has vertices $1,2,3,4,5$ and edges $12,23,34,45$. We mark the edge $34$.
  5. Vertex $3$ is an outer vertex of $F$, and there is an unmarked edge $35$. It goes to another outer vertex of $F$, $5$ (it's at level $4$). These vertices have the same root, $1$, so we contract the blossom formed by edge $35$ and the unique path from $3$ to $5$ in $F$.
$\endgroup$
3
  • $\begingroup$ I don't understand why "In your example, before we've discovered edge $35$, $F$ will consist of the path from $1$ to $5$. What if we explore edge $35$ before exploring edge $45$? I've added an image to my original post to better express my point. Also, I would appreciate an explanation that has more to do with the definitions than the implementation of the algorithm. I'm trying to put the horse before the cart, so to speak. $\endgroup$
    – Nu Nunu
    Dec 4 '19 at 12:36
  • $\begingroup$ If you explore explore edge $35$ first, then it and edge $54$ will be added to the matching, and edge $34$ will connect two outer vertices. The explanation having to do with the definitions is given with the very first sentence of my answer, which tells you what you're missing: the labeling is done with respect to distances in the forest $F$, not the entire graph. $\endgroup$ Dec 4 '19 at 14:35
  • $\begingroup$ In this diagram, the "horizontal" edge $45$ will never be the last edge of the cycle you consider: it will get added to $F$ as soon as you get to vertex $4$ or $5$. $\endgroup$ Dec 4 '19 at 14:37

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.