We continue with matchings in simple graphs, following the exposition in A.Schrijver’s 3-volume work, and his lecture notes available online, filling in few more details.

While in a bipartite graph and a matching it is always the case that a shortest path from the set of -unsaturated vertices to itself (i.e. an –-path) is always -augmenting, this is no longer true in general graphs:

here , is indicated by thicker edges, and the shortest path (of length 4) between them is not augmenting. This precludes the algorithmic idea of augmenting a matching using an augmenting path (found by a shortest path procedure in a digraph constructed from and ) from working in the general case. Edmonds came up with an idea that one can allow for repeated vertices, and shink the arising in the process cycles to (new) vertices.

Definition 1An -alternating walk is a sequence of vertices (some of which can repeat!) that is a walk (i.e. for all ) so that exactly one of and is in .

Definition 2An -alternating walk is an –flowerif has an even number of vertices (as a sequence, i.e. is odd), , all the are distinct, and for (Removing the vertex and the edge on the picture above is an example of an -flower).

The cycle in an -flower is an –blossom.( on the picture above is an example of an -blossom.)

Once we have an -blossom , we can *shrink* it by replacing all of its vertices with just one vertex (call it , too), replacing each edge , with the edge (and ignoring any loops that arise on ). The resulting graph is denoted by . (E.g. shrinking the -blossom on the picture above produces the graph that is the path ). In one will have the matching , where will become just a saturated vertex.

Theorem 3is a maximum matching in if and only if is a maximum matching in , for an -blossom .

*Proof:* If is not a maximum matching in then there will be an -augmenting path in If does not meet then it corresponds to an -augmenting path in . So we can assume that is an edge of , and is also an edge of . As , there exists so that Now, depending upon the parity of , we replace in by the part of the blossom rim , where the sign in the indices is for odd, and for even.

Conversely, if is not a maximum matching in , then

is also a matching of the same size, and . Thus it suffices to show that is not maximal in , and we will assume w.l.o.g. that , i.e. (our flower has no stem). There exists an -augmenting path . W.l.o.g. does not start in (we can reverse it if it does). If does not contain a vertex in , it will continue to be an augmenting path in . Otherwise let the first vertex of in be . Then is an augmenting path in .

For the algorithm we will need

Theorem 4A shortest to -alternating walk is either a path or its initial segment is an -flower.

*Proof:* Assume is not a path, and let be such that and as small as possible. We will show that is an -flower, and we immediately have it if is even and is odd.

If were even, as shown above, where the walk might have been , and so , , then the path is -alternating, so we would simply delete it from and obtain a shorter -alternating walk.

If were odd and even, we would have and in , so , contradicting the choice of .

Combining these two observations, we obtain the following augmenting path algorithm:

- Input: a graph and a matching .
- Let be the set of vertices unsaturated by . Construct, if possible, a positive length shortest walk from to .
- If no was constructed, return — is maximum.
- If is a path then return it.
- Otherwise take the first blossom from , call the algorithm recursively on and , and return the expanded to an augmenting path in resulting path in .

Applying the algorithm starting from , and augmenting with the path it returns, we obtain an efficient algorithm, running in fact in operations.

We still need to discuss here how to do Step 2. To this end we construct a directed graph with

Lemma 5Each to -alternating path, resp. each -flower, corresponds to a directed path in from to —the set of neighbours of in Conversely, each to directed path in corresponds either to an -augmenting path or to an -flower.

*Proof:* (Sketch) Each length 1 -augmenting path obviously corresponds to the pair of arcs and in .

If is a -path in , so that , , then there is a unique, up to the choice of , lifting of it to an -alternating walk , with for . If is a path then it is -augmenting.

If has repeated vertices, this repetition occurs in a regular way, corresponding to an -flower. As we move along from to , let , , be the first repetition. Then is the beginning of the blossom, and the last vertex of the blossom.

Tags: graph theory, MAS324

5 October, 2010 at 14:25 |

Thanks for the post (and for your other posts too)!

The pictures seem to link to pdfs. Are my browsers too old that they don’t show pdfs, or did you mean to link to another format?

5 October, 2010 at 14:33 |

Thanks for pointing this out. It works on MacOSX/Safari, but as I just checked, does not work for e.g. Chrome on Linux…

I’ll fix it shortly.

5 October, 2010 at 14:51 |

should be OK now

5 October, 2010 at 15:15 |

thank you, it works