Edmonds algorithm for maximum matchings

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 {\Gamma=(V,E)} and a matching {M\subset E} it is always the case that a shortest path from the set {X\subset V} of {M}-unsaturated vertices to itself (i.e. an {X}{X}-path) is always {M}-augmenting, this is no longer true in general graphs:

here {X=\{a,b\}}, {M} 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 {M} using an augmenting path (found by a shortest path procedure in a digraph constructed from {\Gamma} and {M}) 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 1 An {M}-alternating walk {P=(v_0,\dots,v_t)} is a sequence of vertices (some of which can repeat!) that is a walk (i.e. {v_i v_{i+1}\in E} for all {0\leq i\leq t-1}) so that exactly one of {v_{i-1} v_i} and {v_i v_{i+1}} is in {M}.

Definition 2 An {M}-alternating walk {P=(v_0,\dots,v_t)} is an {M}flower if {P} has an even number of vertices (as a sequence, i.e. {t} is odd), {v_0\in X}, all the {v_0,\dots,v_{t-1}} are distinct, and {v_t=v_{2k}} for {2k<t.} (Removing the vertex {b} and the edge {bs} on the picture above is an example of an {M}-flower).
The cycle {(v_{2k},v_{2k+1},\dots, v_t)} in an {M}-flower is an {M}blossom. ({(qvuts)} on the picture above is an example of an {M}-blossom.)

Once we have an {M}-blossom {B}, we can shrink it by replacing all of its vertices {V(B)} with just one vertex (call it {B}, too), replacing each edge {uv}, {v\in V(B)} with the edge {uB} (and ignoring any loops that arise on {B}). The resulting graph is denoted by {\Gamma/B=(V/B, E/B)}. (E.g. shrinking the {M}-blossom {B} on the picture above produces the graph that is the path {apBb}). In {\Gamma/B} one will have the matching {M/B}, where {B} will become just a saturated vertex.

Theorem 3 {M} is a maximum matching in {\Gamma} if and only if {M/B} is a maximum matching in {\Gamma/B}, for an {M}-blossom {B}.

Proof: If {M/B} is not a maximum matching in {\Gamma/B} then there will be an {M/B}-augmenting path {P} in {\Gamma/B.} If {P} does not meet {B=(v_{2k},\dots,v_t)} then it corresponds to an {M}-augmenting path {P'} in {\Gamma}. So we can assume that {uB\not\in M} is an edge of {P}, and {Bu'\in M} is also an edge of {P}. As {uB\in E/B}, there exists {2k\leq j<t} so that {uv_j\in E.} Now, depending upon the parity of {j}, we replace {B} in {P} by the part of the blossom rim {v_j,v_{j\pm 1},v_{j\pm 2},\dots,v_t}, where the sign in the indices is {+} for {j} odd, and {-} for {j} even.

Conversely, if {M'} is not a maximum matching in {\Gamma}, then

\displaystyle M=M'\Delta \{v_0v_1,\dots,v_{2k-1}v_{2k}\}

is also a matching of the same size, and {|M/B|=|M'/B|}. Thus it suffices to show that {M/B} is not maximal in {\Gamma/B}, and we will assume w.l.o.g. that {k=0}, i.e. {v_{2k}=v_0\in X} (our flower has no stem). There exists an {M}-augmenting path {P=(u_0,\dots,u_s)}. W.l.o.g. {P} does not start in {B} (we can reverse it if it does). If {P} does not contain a vertex in {B}, it will continue to be an {M/B} augmenting path in {\Gamma/B}. Otherwise let the first vertex of {P} in {B} be {u_j}. Then {(u_0,\dots,u_{j-1},B)} is an augmenting path in {\Gamma/B}. \Box

For the algorithm we will need

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

Proof: Assume {P=(v_0,\dots,v_t)} is not a path, and let {i<j} be such that {v_i=v_j} and {j} as small as possible. We will show that {(v_0,\dots,v_j)} is an {M}-flower, and we immediately have it if {i} is even and {j} is odd.

If {j-i} were even, as shown above, where the walk might have been {(apqstpqb)}, and so {j=5}, {i=1}, then the path {(v_i,\dots,v_{j-1})} is {M}-alternating, so we would simply delete it from {P} and obtain a shorter {M}-alternating walk.

If {i} were odd and {j} even, we would have {v_iv_{i+1}} and {v_{j-1}v_j} in {M}, so {v_{i+1}=v_{j-1}}, contradicting the choice of {j}. \Box

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

  1. Input: a graph {\Gamma} and a matching {M}.
  2. Let {X} be the set of vertices unsaturated by {M}. Construct, if possible, a positive length shortest walk {P} from {X} to {X}.
  3. If no {P} was constructed, return {\emptyset}{M} is maximum.
  4. If {P} is a path then return it.
  5. Otherwise take the first blossom {B} from {P}, call the algorithm recursively on {\Gamma/B} and {M/B}, and return the expanded to an augmenting path in {\Gamma} resulting path in {\Gamma/B}.

Applying the algorithm starting from {M=\emptyset}, and augmenting {M} with the path it returns, we obtain an efficient algorithm, running in fact in {O(|V|^2|E|)} operations.

We still need to discuss here how to do Step 2. To this end we construct a directed graph {D_M=(V,A\cup A')} with

\displaystyle A:=\{(u,v)\mid u\neq v\in V, \exists ux\in E, xv\in M\}

\displaystyle A':=\{(u,v)\mid u\neq v\in X, \exists uv\in E\}

Lemma 5 Each {X} to {X} {M}-alternating path, resp. each {M}-flower, corresponds to a directed path in {D} from {X} to {\Gamma(X)}—the set of neighbours of {X} in {\Gamma.} Conversely, each {X} to {\Gamma(X)} directed path in {A} corresponds either to an {M}-augmenting path or to an {M}-flower.

Proof: (Sketch) Each length 1 {M}-augmenting path {uv} obviously corresponds to the pair of arcs {uv} and {vu} in {A'}.

If {u_0,u_1,\dots,u_s} is a {A}-path in {D}, so that {u_0\in X}, {u_t\in\Gamma(X)}, then there is a unique, up to the choice of {u_{s+1}\in X}, lifting of it to an {M}-alternating walk {P=u_0,v_1,u_1,v_2,u_2,\dots,v_s,u_s,u_{s+1}}, with {v_iu_i\in M} for {1\leq i\leq s}. If {P} is a path then it is {M}-augmenting.

If {P} has repeated vertices, this repetition occurs in a regular way, corresponding to an {M}-flower. As we move along {P} from {u_0} to {u_s}, let {u_t=v_i}, {t>i}, be the first repetition. Then {u_i} is the beginning of the blossom, and {u_{t-1}} the last vertex of the blossom. \Box


Tags: ,

4 Responses to “Edmonds algorithm for maximum matchings”

  1. val Says:

    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?

  2. val Says:

    thank you, it works

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: