Definition Given a graph , a matching is a set of edges where no two edges share a vertex.
Definition A perfect matching is a matching that has size , i.e. every vertex in the graph is matched.
Problem Find a maximum cardinality (size) matching of a graph .
Problem Does have a perfect matching? (PM)
For these notes, we will consider matchings on bipartite graphs, a natural and useful class of graphs. In the next lecture, we will extend the matching algorithm to general graphs.
Definition A graph for vertex sets is bipartite if every edge in has one vertex in and one vertex in .
First, is PM in NP? Yes, output the matching and check that each vertex has degree exactly .
Is PM in Co-NP? The following theorem gives the existence of a short certificate.
Theorem(Konig-Hall) A bipartite graph has a perfect matching iff
- Both sides of the bipartition have the same number of vertices:
- For all subsets , the size of ‘s neighbors is greater than the size of : .
() It is clear that having a perfect matching implies the conditions are satisfied.
() Assume satisfies conditions 1 and 2 above. We will prove by induction on the size of .
- This is a graph with two vertices and one edge between them. Thus has a perfect matching.
- Case 1: , i.e. strictly greater than, for all subsets . Then, select any edge and match this edge. By induction, the graph has a perfect matching.
- Case 2: There exists a subset such that . We then induct on and .
Algorithms for Maximum Bipartite Matching
Definition An alternating path in with respect to a matching is a path whose edges alternate in and out of the matching .
Definition An augmenting path in is an alternating path with both endpoints unmatched.
Lemma is maximum iff has no augmenting paths with respect to .
() Suppose is a maximum matching. Then, there are no augmenting paths, since if has an augmenting path, we augment along it and increase the size of .
() Suppose we have no augmenting paths for a matching . Let be a maximum matching. (GOAL: show )
Consider the symmetric difference , the set of edges in one of but not the other.
Then, the set of vertices in have degree either . Therefore, is a set of paths and cycles. We know that every cycle must be even length since both are matchings. Further, we know that every path must also be even length, since an odd length path would imply an augmenting path for either or . Therefore, the size of are equal, and thus is a maximum matching.
So we have proved that a matching is maximum iff there is no augmenting path with respect to . Thus, the following general algorithm can be used to compute a maximum matching.
- While (there exists an augmenting path)
- Find an augmenting path with respect to
- Augment with
In case of bipartite graphs, there is an easy algorithm to compute augmenting paths. Let the bipartition of graph be . Let the unmatched vertices of be denoted by .
- Initialize a forest
- While (no new vertices can be added to )
- Add all vertices of to
- Add edges to new vertices in while maintaining a forest
- If any of the vertices in is unmatched, then there is an augmenting path, so output it and exit
- Add matched edges from the new vertices in
Proof of correctness:
A vertex cover is a set such that every edge in the graph is incident to at least one vertex in .
Lemma: The size of any vertex cover is greater than or equal to the size of any matching
Proof: Since any vertex cover covers all edges in the graph, it must contain at least one endpoint from any edge in a matching, as the edges in a matching have no common endpoint.
Corollary: If there is a matching and vertex cover s.t. , then is a maximum matching and is a minimum vertex cover
Let be the forest output by the algorithm.
It is easy to verify that
Claim: is a vertex cover
Proof: Suppose that an edge is not covered by . Then clearly, and . This is a contradiction since the algorithm would have added the edge to grow the forest further. But the forest cannot be grown further. This contradiction implies is a vertex cover.
Since , we conclude that is a maximum matching. Thus, the algorithm terminates only when the matching found is a maximum matching.