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.