# 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$.