Recall the following theorem we proved in the last lecture.
Theorem: For any bipartite graph 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 while the size of the maximum matching is .
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 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 let us denote by the number of odd sized components in . Notice the following necessary condition for a perfect matching to exist in :
Lemma: If there exists a subset such that then cannot have a perfect matching.
Proof: Suppose not and there is a perfect matching in . Notice that 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 . However which is a contradiction since by the pigeon hole principle there must be two matching edges incident on the same vertex in .
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 a blossoms is a cycle of length with exactly matched edges, for any positive integer .
Lemma: Let be a blossom of and is disjoint from the rest of . Let be the graph obtained from by shrinking the blossom to a single vertex and let be the matching restricted to . Then has an -augmenting path if and only if has an -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 that ends at the blossom vertex (notice that the blossom vertex is unmatched in ). Then since the blossom is an odd cycle there must be a path in to the unmatched vertex in the blossom. Similarly if we have an augmenting path in that hits the blossom at some vertex, then we get a corresponding augmenting path in 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 be all the unmatched vertices of
- For every outer and with add and to where is a matching edge.
- For outer from different components of , if then we found an augmenting path.
- For outer from same component and
- Identify blossom (Least Common Ancestor of )
- 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 in the set of outer vertices we must have is a subset of inner vertices. This is because otherwise we found a blossom and would contract it and proceed. Let be the number of inner vertices and the set of outer vertices. Note that . Let be the set of all the inner vertices, then observe that each outer vertex is a singleton component in . Thus . Thus the number of unmatched vertices must be at least since we can match the unmatched vertices in the odd components to at most vertices in . Thus must be a maximum matching in , where is obtained by shrinking each blossom. Thus is a maximum matching in which implies by the previous lemma that is a maximum matching in .
Running time: The run time is since doing the BFS procedure takes steps, the matching size increases by each time we find an augmenting path and we can find at most blossoms in .
Note that the above algorithm implies the other direction of Tutte’s theorem.