Feb 23. Matchings in bipartite graphs

Matching

A matching M is a subset of E such that no two edges e, e' \in M share a vertex, i.e. for any two edges e, e' \in M we have e \cap e' = \phi.

Perfect Matching

A perfect matching is a matching that meets every vertex of G, i.e. for every v \in V there is an edge (u,v) \in M.

Problem: Given a bipartite graph G we wish to know whether G has a perfect matching. Note that the yes answer has a short certificate, namely the perfect matching itself. The certificate for the no answer follows from Hall’s theorem which we give below.

Hall’s Theorem: G=(V=A \cup B, E) has a perfect matching if and only if |A| = |B| and \forall X \subseteq A, |N(X)| \ge |X|.

Proof: Note that the forward direction is trivial. Suppose for every X \subsetneq A, |N(X)| > |X| then we are done by induction on the number of vertices. Consider an edge e=(u, v) and let G' = G\setminus \{u,v\}. Let V(G') = A' \cup B'. Then clearly |A'| = |B'| and \forall X \subseteq A, |N(X)| \ge |X|. Thus by our inductive hypothesis we are done.

Now suppose there is a set X \subsetneq A such that |N(X)| = |X|. Consider the graph H induced on X \cup N(X). Since |X| < |A| and so by induction we know that there is a perfect matching in H. Let us consider the induced graph H' on (A\setminus N(X)) \cup (B \setminus N(X)). We claim that for every Y \subseteq B \setminus N(X), |N(Y)| \ge |Y|. This is because if |A|=|B| then \forall X \subseteq A, |N(X)| \ge |X| if and only if \forall Y \subseteq B, |N(Y)| \ge |Y|. Thus applying the inductive hypothesis we get a perfect matching in H'. Patching the perfect matchings in H and H' gives us a perfect matching in G.

Algorithm

Alternating path: A path P in a graph is an M alternating path if the edges in the path alternate between M and non M edges.

Augmenting path: An M augmenting path is an M alternating path such that its two end points is M unmatched.

Suppose we have an M augmenting path P. Then we can construct a new matching M' = M \triangle P. Note that |M'| > |M|. This step is called augmenting the augmenting path P. Thus if we have the following algorithm:

  • Start with an arbitrary matching M.
  • While there exists an M augmenting path P:
  • Augment path P
  • Set M = M \triangle P
  • EndWhile

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

Proof: Clearly if M is a maximum matching then G can have no M augmenting path since augmenting it would produce a matching M' such that |M'| > |M|.

Suppose M has no augmenting path and let N be a maximum matching. Consider M \triangle N. Notice that the degree of any vertex v in M \triangle N is at most 2. This is because any vertex can have at most 1 M edge and at most 1 N edge incident on it. Observe that this implies M \triangle N must be a disjoint collection of paths and cycles. Note that every cycle must be of even length since the cycle edges alternate between M and N. Thus the number of M edges in cycles is the same as the number of N edges. In even paths the number of M edges is the same as the number of N edges since they are alternating. Suppose we have an odd length path. There are two possibilities – either it ends with an M edge in which case it is N augmenting (contradiction since N is maximum) or it ends with an N edge in which case it is M augmenting (contradicting our hypothesis). Thus M\triangle N consists of only even cycles and even paths. Thus |M| = |N|.

Finding augmenting paths

Start with all the unmatched vertices and consider a BFS like procedure from them. We grow the forest around them by adding unmatched and matched edges alternatively. Notice that there cannot be an unmatched edge connecting two matched vertices in the same component – since that gives us an odd cycle. Whenever two components are connected – we get an augmenting path.

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