Why only odd cycles make problems when searching for augmenting paths to improve the matching(->blossom algorithm)?

Question

I don't understand why only the odd cycles in a graph make problems, when searching for augmenting paths. As far as I understood in an odd cycle the search algorithm(bfs for example) kind of splits in this cycle and the two searches meet somewhere in the middle of the cycle. The big augmenting path which uses the cycle is therefore not found. Why can't this happen with cycles of even degree?

Answer 1

First, if the graph is an odd cycle, the search algorithm always finds an augmenting path (if there is one), so it is not just a question of having an odd cycle. Actually, a closer look at Edmonds' algorithm will show you that only some very specific odd cycles are problematic: those with $k$ edges in $M$ where $2k+1$ is their length.

What is true is that in the absence of odd cycle, it works fine. My understanding is that the search algorithm tries to partition the vertex set of the graph into:

• a set of vertices reachable from an uncovered vertex by an odd-length alternating path,
• a set of vertices reachable from an uncovered vertex by an even-length alternating path,
• the remaining vertices, unreachable by alternating paths.

The algorithm may only fail in finding a vertex that is reachable by alternating paths both of even and odd length. In that case, if the graph is bipartite, it is not hard to find an augmenting path (see below).

If the graph is non-bipartite, because of odd cycles, there may be vertices reachable by alternating paths both of even and odd lengths, while no augmenting paths exists, breaking the simple partition scheme.

To go deeper, let's see why we can find an augmenting paths in the case of bipartite graphs, as soon as we find two paths: an odd alternating path $P_u$ from $u$ to $v$ and an even alternating path $P_w$ from $w$ to $v$, where $u$ and $w$ are not covered by the current matching $M$. If $P_u$ and $P_w$ are inner disjoint, then the concatenation $P_u \circ \textrm{rev}(P_w)$ is an augmenting path. Otherwise, consider $x$ the vertex of $P_u$ closest to $u$ such that $x \in P_w$. Then $P_w[w \to x] \circ P_u[x \to v]$ is an augmenting path (locally at vertex $x$, $P_w$ directed from $w$ to $v$ enters by the edge $m \in M$ incident to $x$ while $P_u$ from $u$ to $v$ must leave by $m$). Here we do not use the bipartiteness. Rather we use the fact that $u$ and $w$ are distinct vertices. This cannot happen in bipartite graphs, as there is a walk $P_u \circ rev(P_w)$ from $u$ to $w$ of odd length, thus $u$ and $w$ are not on the same side of the bipartition, and thus are distinct. Observe that the augmenting path is made of the concatenation of two paths from the search algorithm, so what you describe as the fact that the search splits in a cycle is not really relevant: even if a cycle is split, most of its edges may end up in the augmenting path.