Recall the lemma we proved last time.
Lemma: is a maximum matching in if and only if has no augmenting paths.
Let the two bipartitions of be and . Let us denote the unmatched vertices in by . We then have the following algorithm:
- Let be a forest, initialized to be empty.
- While True:
- Add all vertices of to .
- Add edges to vertices in , maintaining a forest (add only one edge to a new vertex in ).
- If any of the vertices in is unmatched then we found an augmenting path, exit loop.
- Add matched edges from new vertices of .
- If no new vertices can be added, exit
Note that this is like a BFS from multiple sources (namely the vertices in ) where we alternate between matched and unmatched edges. Note that the first level of vertices is in (namely ), the second level is in , the third in and so on. Thus there cannot be any edge between the same level in this BFS tree (since is bipartite). If any path ends in an unmatched vertex then we end up with an augmenting path since the source vertices are in . Thus we may assume that every path down from ends in a matched edge.
Vertex Cover: A vertex cover is a subset such that every edge in has atleast one endpoint in .
Lemma: For any vertex cover and for any matching we must have . Thus it implies that .
Proof: Since every edge has to be covered (in particular the edges of ) and since no two edges of are incident on the same vertex, it follows that we must pick atleast unique vertex to cover every edge of .
Theorem: If the algorithm above terminates without finding an augmenting path then must be a maximum matching.
Proof: We will prove this by exhibiting a vertex cover of the same size as the matching . Define . Note that the . Suppose is not covered by . Then clearly and . This is a contradiction since the algorithm would then have added to grow the forest further. However the forest cannot be grown any further.
Running Time: A naive implementation of this algorithm would take time since the maximum matching can grow only up to and finding an augmenting path takes .
Alternate Implementation: Augment on a maximal set of disjoint shortest augmenting paths.
Observation (Extra credit): The length of the shortest augmenting path increases after each augmenting phase.
Theorem: Suppose the above observation is true then the the number of phases is . This implies a running time of .
Proof: Let be the matching after phases. Thus the length of any augmenting path is greater than or equal to . If is a maximum matching, then . Thus after at most more phases we will be done. To see this look at . On the even paths and cycles the number of and is exactly equal. On odd paths the number of edges is exactly one more than the number of edges. However each such path is an augmenting path and so has length at least . Since these are disjoint paths and each path gives exactly one more extra edge in , it follows that the number of extra edges in is at most .