General Graph Matching

Tutte’s Theorem: graph G = (V, E) has perfect matching M if and only if for all subsets X \subseteq V,

|odd(G \setminus X)| \le |X|

where |odd(G \setminus X)| denotes the number of odd components in the subgraph G \setminus X.

To demonstrate forward direction, assume towards contradiction that G has perfect matching M and there exists subset X \subseteq V such that |odd(G \setminus X)| > |X|. Note that no two distinct odd components in G \setminus X can share the same vertex in X, since the edges should constitute a matching. Thus, there exists some odd component with no matching edge to verses in X, which yields a contradiction

The other direction can be proved by first proving the correctness of Edmond’s algorithm, which computes maximum matchings for general graphs.

Edmond’s Algorithm:

For a matching M, a blossom is an odd cycle of length 2k+1 with k edges from M.

Lemma: Let B be a blossom of G such that B is disjoint from the rest of M. Let G' be the graph obtained from G by contracting the blossom B to a single vertex and let M' be the matching M restricted to G'. Then, G has an augmenting path iff G' has an augmenting path.

Proof: Clearly, if no augmenting path meets B, then the statement is trivial in both directions. Suppose we have an augmenting path in G' that ends at the blossom vertex (notice that the blossom vertex is unmatched in M'). Since the blossom is an odd cycle, there must be a path in G to the unmatched vertex in the blossom. Similarly, if we have an augmenting path in G that meets the blossom at some vertex, then we get a corresponding augmenting path in G' that ends at the blossom vertex.

With this idea, it is possible to modify the augmenting path algorithm from bipartite graphs to work for general graphs. Let the vertices on the even level be called outer vertices and the vertices on the odd levels be called inner vertices.

  • Let F be forest with roots initialized as all unmatched vertices in G
  • For every outer x \in F and y \notin F with (x,y) \in E, add (x,y) and (y,z) to F where (y,z) is a matching edge.
  • For outer x,y from different components of F, if (x,y) \in E, then we found an augmenting path, so output it and exit
  • For outer x,y from the same component and (x,y) \in E
    • Identify blossom (Least Common Ancestor of x,y)
    • Shrink the blossom, swap the matching and non matching edges from the blossom vertex to the root of its component.
  • Repeat till either augmenting path is found or if no more new vertices can be added.

Time Complexity: The running time is O(m n^2) since we perform graph search which takes O(m) steps, the size of the matching increases by 1 every time we find an augmenting path, and there can be at most \frac{n}{2} blossoms in the graph.

Correctness: 

We have proved (in previous lecture) that G is a maximum matching if and only if there are no augmenting paths. Suppose that Edmond’s algorithm does not find an augmenting path. But does this mean there are no augmenting paths? Is Edmond’s algorithm guaranteed to find an augmenting path in a graph if it exists?

First, observe that there are no edges between outer vertices:

  1. If there is an edge between outer vertices in the same component of the forest, then this implies a blossom.
  2. If there is an edge between outer vertices in different components, then this implies an augmenting path.

Claim For a subset X \subseteq V that leaves k isolated odd components in G \backslash X, then the number of unmatched vertices in any matching is at least k-|X|.

Proof The claim follows from the following observation: there must be at least one unmatched vertex in each odd component, and for this vertex to be matched, it must be matched to a vertex in X.

Proof (Edmond’s algorithm) Take X the be all inner vertices, which leaves a number of isolated odd components equal to the number of outer vertices. Thus, the number of unmatched vertices in any matching is at least #outer-#inner vertices. Note that #outer-#inner is equal to the number of components in the forest found by Edmond’s algorithm, which is also equal to the number of unmatched vertices. Thus, if Edmond’s algorithm does not find an augmenting path, then the matching is maximum!

Corollary (Tutte’s Theorem) G has a perfect matching iff for all X \subseteq V, |X| \ge |odd(G\backslash X)|.

 

Advertisements

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s