Bipartite Matching

PDF of Prof. Santosh’s handwritten notes is here.

Matchings

Definition Given a graph G=(V,E), a matching M \subseteq E is a set of edges M = \{e_1, e_2, \ldots, e_k\} where no two edges share a vertex.

Definition perfect matching is a matching that has size |V|/2, i.e. every vertex in the graph is matched.

Problem Find a maximum cardinality (size) matching of a graph G.

Problem Does G 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 G = (A,B,E) for vertex sets A, B is bipartite if every edge in E has one vertex in A and one vertex in B.

First, is PM in NP? Yes, output the matching and check that each vertex has degree exactly 1.

Is PM in Co-NP? The following theorem gives the existence of a short certificate.

Theorem(Konig-Hall) A bipartite graph G=(A,B,E) has a perfect matching iff

  1. Both sides of the bipartition have the same number of vertices: |A|=|B|
  2. For all subsets X \subseteq A, the size of X‘s neighbors is greater than the size of X: |N(X)| \ge |X|.

Proof.

(\Rightarrow) It is clear that G having a perfect matching implies the conditions are satisfied.

(\Leftarrow) Assume G satisfies conditions 1 and 2 above. We will prove by induction on the size of A.

  • |A|=1
    • This is a graph G with two vertices and one edge between them. Thus G has a perfect matching.
  • |A|>1
    • Case 1: |N(X)| > |X|, i.e. strictly greater than, for all subsets X \subsetneq A. Then, select any edge e = (u,v) and match this edge. By induction, the graph G \backslash \{u,v\} has a perfect matching.
    • Case 2: There exists a subset X \subsetneq A such that |N(X)|=|X|. We then induct on M_X = (X, N(X)) and M_{A \backslash X}=(A \backslash X, B \backslash N(X)).

Algorithms for Maximum Bipartite Matching

Definition An alternating path in G with respect to a matching M is a path whose edges alternate in and out of the matching M.

Definition An augmenting path in G is an alternating path with both endpoints unmatched.

Lemma M is maximum iff G has no augmenting paths with respect to M.

Proof.

(\Rightarrow) Suppose M is a maximum matching. Then, there are no augmenting paths, since if G has an augmenting path, we augment along it and increase the size of M.

(\Leftarrow) Suppose we have no augmenting paths for a matching M. Let N be a maximum matching. (GOAL: show |M|=|N|)

Consider the symmetric difference M \oplus N, the set of edges in one of M,N but not the other.

Then, the set of vertices in M \oplus N have degree either 0, 1, 2. Therefore, M \oplus N is a set of paths and cycles. We know that every cycle must be even length since both M,N 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 M or N. Therefore, the size of M,N are equal, and thus M is a maximum matching.

So we have proved that a matching M is maximum iff there is no augmenting path with respect to M. Thus, the following general algorithm can be used to compute a maximum matching.

  • While (there exists an augmenting path)
    • Find an augmenting path P with respect to M
    • Augment M with P

In case of bipartite graphs, there is an easy algorithm to compute augmenting paths. Let the bipartition of graph G be A, B. Let the unmatched vertices of A be denoted by A^U.

Algorithm:

  • Initialize a forest F = \phi
  • While (no new vertices can be added to F)
    • Add all vertices of A^U to V(F)
    • Add edges to new vertices in B while maintaining a forest
    • If any of the vertices in B is unmatched, then there is an augmenting path, so output it and exit
    • Add matched edges from the new vertices in B

Proof of correctness:

A vertex cover is a set S \subseteq V such that every edge in the graph is incident to at least one vertex in S.

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 M and vertex cover S s.t. |M| = |S|, then M is a maximum matching and S is a minimum vertex cover

Let F be the forest output by the algorithm.

Let S = (B \cap V(F)) \cup (A \setminus V(F))

It is easy to verify that |S| = |M|

Claim: S is a vertex cover

Proof: Suppose that an edge (u,v) \in E is not covered by S. Then clearly, u \in V(F)\cap A and v \notin V(F). This is a contradiction since the algorithm would have added the edge (u,v) to grow the forest further. But the forest cannot be grown further. This contradiction implies S is a vertex cover.

Since |S| = |M|, we conclude that M is a maximum matching. Thus, the algorithm terminates only when the matching found is a maximum matching.

Advertisements

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