Feb 27. Matchings in bipartite graphs II

Recall the lemma we proved last time.

Lemma: M is a maximum matching in G if and only if G has no M augmenting paths.

Let the two bipartitions of G be A and B. Let us denote the unmatched vertices in A by A^U. We then have the following algorithm:

  • Let F be a forest, initialized to be empty.
  • While True:
    • Add all vertices of A^U to V(F).
    • Add edges to vertices in B, maintaining a forest (add only one edge to a new vertex in B).
    • If any of the vertices in B is unmatched then we found an augmenting path, exit loop.
    • Add matched edges from new vertices of B.
    • If no new vertices can be added, exit

Note that this is like a BFS from multiple sources (namely the vertices in A^U) where we alternate between matched and unmatched edges. Note that the first level of vertices is in A (namely A^U), the second level is in B, the third in A and so on. Thus there cannot be any edge between the same level in this BFS tree (since G is bipartite). If any path ends in an unmatched vertex then we end up with an augmenting path since the source vertices are in A^U. Thus we may assume that every path down from A^U ends in a matched edge.

Vertex Cover: A vertex cover is a subset S \subseteq V such that every edge in E has atleast one endpoint in S.

Lemma: For any vertex cover S and for any matching M we must have |S| \ge |M|. Thus it implies that \min_{S: S \text{is a vertex cover}} |S| \ge \max_{M: M \text{is a matching}} |M|.

Proof: Since every edge has to be covered (in particular the edges of M) and since no two edges of M are incident on the same vertex, it follows that we must pick atleast 1 unique vertex to cover every edge of M.

Theorem: If the algorithm above terminates without finding an augmenting path then M must be a maximum matching.

Proof: We will prove this by exhibiting a vertex cover S of the same size as the matching M. Define S = (B\cap V(F)) \cup (A \setminus V(F)). Note that the |S| = |M|. Suppose (a, b) \in E is not covered by S. Then clearly a \in V(F) and b \notin V(F). This is a contradiction since the algorithm would then have added (a,b) to grow the forest further. However the forest cannot be grown any further.

Running Time: A naive implementation of this algorithm would take O(mn) time since the maximum matching can grow only up to n/2 and finding an augmenting path takes O(m).

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 O(\sqrt{n}). This implies a running time of O(m\sqrt{n}).

Proof: Let M be the matching after \sqrt{n} phases. Thus the length of any augmenting path is greater than or equal to 2\sqrt{n} + 1. If N is a maximum matching, then |N| - |M| \le \frac{\sqrt{n}}{2}. Thus after at most \sqrt{n}/2 more phases we will be done. To see this look at M \triangle N. On the even paths and cycles the number of M and N is exactly equal. On odd paths the number of N edges is exactly one more than the number of M edges. However each such path is an M augmenting path and so has length at least 2\sqrt{n} + 1. Since these are disjoint paths and each path gives exactly one more extra edge in N, it follows that the number of extra edges in N is at most n/(2\sqrt{n}+2) < \sqrt{n}/2.

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