Mar 02. Matching in general graphs.

Recall the following theorem we proved in the last lecture.

Theorem: For any bipartite graph G the size of the minimum vertex cover equals the size of the maximum matching.

Note that this is not true for graphs that are non-bipartite – an easy example is the triangle. The minimum size of a vertex cover is 2 while the size of the maximum matching is 1.

To find an algorithm for finding a maximum matching in general graphs, we could first establish that Perfect Matching for general graphs is in NP \cap co-NP. Clearly the NP certificate is a perfect matching in the graph. For the co-NP certificate we make the following observation. For any subset X\subseteq V let us denote by o(G\setminus X) the number of odd sized components in G\setminus X. Notice the following necessary condition for a perfect matching to exist in G:

Lemma: If there exists a subset X \subseteq V such that o(G\setminus X) > |X| then G cannot have a perfect matching.

Proof: Suppose not and there is a perfect matching M in G. Notice that M restricted to the odd component cannot be a perfect matching inside that component since the size of the component is odd. Thus there must be a matching edge from each of the odd sized component to X. However |X| < o(G\setminus X) which is a contradiction since by the pigeon hole principle there must be two matching edges incident on the same vertex in X.

As it turns out the above necessary condition is also sufficient. This theorem is called Tutte’s theorem. Let us make the following definition.

Blossom: Given a matching M a blossoms is a cycle of length 2k+1 with exactly k matched edges, for any positive integer k.

Lemma: Let B be a blossom of G and B is disjoint from the rest of M. Let G' be the graph obtained from G by shrinking the blossom B to a single vertex and let M' be the matching M restricted to G'. Then G has an M-augmenting path if and only if G' has an M'-augmenting path.

Proof: Clearly if an augmenting path does not meet the blossom 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'). Then 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 hits the blossom at some vertex, then we get a corresponding augmenting path in G' that ends at the blossom vertex.

We get the following modification to the matching algorithm from bipartite graphs. Let the vertices on the odd level be called outer vertices and the vertices on the even levels be called inner vertices.

  • Let F be all the unmatched vertices of 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.
  • For outer x, y from 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 room of its component.
  • Repeat till either augmenting path is found or if no more new vertices can be added.

If the algorithm cannot make any progress without finding an augmenting path then \forall X in the set of outer vertices we must have N(X) is a subset of inner vertices. This is because otherwise we found a blossom and would contract it and proceed. Let p be the number of inner vertices and q the set of outer vertices. Note that q-p = |U|. Let X be the set of all the inner vertices, then observe that each outer vertex is a singleton component in G\setminus X. Thus o(G\setminus X)=q. Thus the number of unmatched vertices must be at least q-p since we can match the unmatched vertices in the odd components to at most p vertices in X. Thus M' must be a maximum matching in G', where G' is obtained by shrinking each blossom. Thus M' is a maximum matching in G' which implies by the previous lemma that M is a maximum matching in G.

Running time: The run time is O(mn^2) since doing the BFS procedure takes O(m) steps, the matching size increases by 1 each time we find an augmenting path and we can find at most n/2 blossoms in G.

Note that the above algorithm implies the other direction of Tutte’s theorem.

 

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