Now we return to systems of distinct representatives.
A system of distinct representatives corresponds to a set of edges in the corresponding bipartite graph that share no endpoints; such a collection of edges (in any graph, not just a bipartite graph) is called a matching. In figure 4.5.1, a matching is shown in red. This is a largest possible matching, since it contains edges incident with all four of the top vertices, and it thus corresponds to a complete sdr.
Any bipartite graph can be interpreted as a set system: we simply label all the vertices in one part with "set names'' $A_1$, $A_2$, etc., and the other part is labeled with "element names'', and the sets are defined in the obvious way: $A_i$ is the neighborhood of the vertex labeled "$A_i$''. Thus, we know one way to compute the size of a maximum matching, namely, we interpret the bipartite graph as a set system and compute the size of a maximum sdr; this is the size of a maximum matching.
We will see another way to do this working directly with the graph. There are two advantages to this: it will turn out to be more efficient, and as a by-product it will actually find a maximum matching.
Given a bipartite graph, it is easy to find a maximal matching, that is, one that cannot be made larger simply by adding an edge: just choose edges that do not share endpoints until this is no longer possible. See figure 4.5.2 for an example.
An obvious approach is then to attempt to make the matching larger. There is a simple way to do this, if it works: We look for an alternating chain, defined as follows.
Definition 4.5.1 Suppose $M$ is a matching, and suppose that $v_1,w_1,v_2,w_2,\ldots,v_k,w_k$ is a sequence of vertices such that no edge in $M$ is incident with $v_1$ or $w_k$, and moreover for all $1\le i\le k$, $v_i$ and $w_i$ are joined by an edge not in $M$, and for all $1\le i\le k-1$, $w_i$ and $v_{i+1}$ are joined by an edge in $M$. Then the sequence of vertices together with the edges joining them in order is an alternating chain. $\square$
The graph in figure 4.5.2 contains alternating chains, one of which is shown in figure 4.5.3.
Suppose now that we remove from $M$ all the edges that are in the alternating chain and also in $M$, forming $M'$, and add to $M'$ all of the edges in the alternating chain not in $M$, forming $M''$. It is not hard to show that $M''$ is a matching, and it contains one more edge than $M$. See figure 4.5.4.
Remarkably, if there is no alternating chain, then the matching $M$ is a maximum matching.
Theorem 4.5.2 Suppose that $M$ is a matching in a bipartite graph $G$, and there is no alternating chain. Then $M$ is a maximum matching.
Proof. We prove the contrapositive: Suppose that $M$ is not a maximum matching. Then there is a larger matching, $N$. Create a new graph $G'$ by eliminating all edges that are in both $M$ and $N$, and also all edges that are in neither. We are left with just those edges in $M$ or $N$ but not both.
In this new graph no vertex is incident with more than two edges, since if $v$ were incident with three edges, at least two of them would belong to $M$ or two would belong to $N$, but that can't be true since $M$ and $N$ are matchings. This means that $G'$ is composed of disjoint paths and cycles. Since $N$ is larger than $M$, $G'$ contains more edges from $N$ than from $M$, and therefore one of the paths starts and ends with an edge from $N$, and along the path the edges alternate between edges in $N$ and edges in $M$. In the original graph $G$ with matching $M$, this path forms an alternating chain. The "alternating'' part is clear; we need to see that the first and last vertices in the path are not incident with any edge in $M$.
Suppose that the first two vertices are $v_1$ and $v_2$. Then $v_1$ and $v_2$ are joined by an edge of $N$. Suppose that $v_1$ is adjacent to a vertex $w$ and that the edge between $v_1$ and $w$ is in $M$. This edge cannot be in $N$, for then there would be two edges of $N$ incident at $v_1$. But then this edge is in $G'$, since it is in $M$ but not $N$, and therefore the path in $G'$ does not start with the edge in $N$ joining $v_1$ and $v_2$. This contradiction shows that no edge of $M$ is incident at $v_1$. The proof that the last vertex in the path is likewise not incident with an edge of $M$ is essentially identical. $\qed$
Now to find a maximum matching, we repeatedly look for alternating chains; when we cannot find one, we know we have a maximum matching. What we need now is an efficient algorithm for finding the alternating chain.
The key, in a sense, is to look for all possible alternating chains simultaneously. Suppose we have a bipartite graph with vertex partition $\{v_1,v_2,\ldots,v_n\}$ and $\{w_1,w_2,\ldots,w_m\}$ and a matching $M$. The algorithm labels vertices in such a way that if it succeeds, the alternating chain is indicated by the labels. Here are the steps:
0. Label with `(S,0)' all vertices $v_i$ that are not incident with an edge in $M$. Set variable step to 0.
Now repeat the next two steps until no vertex acquires a new label:
1. Increase step by 1. For each newly labeled vertex $v_i$, label with $(i,step)$ any unlabeled neighbor $w_j$ of $v_i$ that is connected to $v_i$ by an edge that is not in $M$.
2. Increase step by 1. For each newly labeled vertex $w_i$, label with $(i,step)$ any unlabeled neighbor $v_j$ of $w_i$ that is connected to $w_i$ by an edge in $M$.
Here "newly labeled'' means labeled at the previous step. When labeling vertices in step 1 or 2, no vertex is given more than one label. For example, in step 1, it may be that $w_k$ is a neighbor of the newly labeled vertices $v_i$ and $v_j$. One of $v_i$ and $v_j$, say $v_i$, will be considered first, and will cause $w_k$ to be labeled; when $v_j$ is considered, $w_k$ is no longer unlabeled.
At the conclusion of the algorithm, if there is a labeled vertex $w_i$ that is not incident with any edge of $M$, then there is an alternating chain, and we say the algorithm succeeds. If there is no such $w_i$, then there is no alternating chain, and we say the algorithm fails. The first of these claims is easy to see: Suppose vertex $w_i$ is labeled $(k_1,s)$. It became labeled due to vertex $v_{k_1}$ labeled $(k_2,s-1)$ that is connected by an edge not in $M$ to $w_i$. In turn, $v_{k_1}$ is connected by an edge in $M$ to vertex $w_{k_2}$ labeled $(k_3,s-2)$. Continuing in this way, we discover an alternating chain ending at some vertex $v_j$ labeled $(S,0)$: since the second coordinate step decreases by 1 at each vertex along the chain, we cannot repeat vertices, and must eventually get to a vertex with $step=0$. If we apply the algorithm to the graph in figure 4.5.2, we get the labeling shown in figure 4.5.5, which then identifies the alternating chain $w_2, v_3,w_1,v_1$. Note that as soon as a vertex $w_i$ that is incident with no edge of $M$ is labeled, we may stop, as there must be an alternating chain starting at $w_i$; we need not continue the algorithm until no more labeling is possible. In the example in figure 4.5.5, we could stop after step 3, when $w_2$ becomes labeled. Also, the step component of the labels is not really needed; it was included to make it easier to understand that if the algorithm succeeds, there really is an alternating chain.
To see that when the algorithm fails there is no alternating chain, we introduce a new concept.
Definition 4.5.3 A vertex cover in a graph is a set of vertices $S$ such that every edge in the graph has at least one endpoint in $S$. $\square$
There is always a vertex cover of a graph, namely, the set of all the vertices of the graph. What is clearly more interesting is a smallest vertex cover, which is related to a maximum matching.
Theorem 4.5.4 If $M$ is a matching in a graph and $S$ is a vertex cover, then $|M|\le |S|$.
Proof. Suppose $M$ is a matching $S$ is a vertex cover. Since each edge of $M$ has an endpoint in $S$, if $|M|> |S|$ then some vertex in $S$ is incident with two edges of $M$, a contradiction. Hence $|M|\le |S|$. $\qed$
Suppose that we have a matching $M$ and vertex cover $S$ for a graph, and that $|M|=|S|$. Then the theorem implies that $M$ is a maximum matching and $S$ is a minimum vertex cover. To show that when the algorithm fails there is no alternating chain, it is sufficient to show that there is a vertex cover that is the same size as $M$. Note that the proof of this theorem relies on the "official'' version of the algorithm, that is, the algorithm continues until no new vertices are labeled.
Theorem 4.5.5 Suppose the algorithm fails on the bipartite graph $G$ with matching $M$. Let $L$ be the set of labeled $w_i$, $U$ the set of unlabeled $v_i$, and $S=L\cup U$. Then $S$ is a vertex cover and $|M|=|S|$.
Proof. If $S$ is not a cover, there is an edge $\{v_i,w_j\}$ with neither $v_i$ nor $w_j$ in $S$, so $v_i$ is labeled and $w_j$ is not. If the edge is not in $M$, then the algorithm would have labeled $w_j$ at the step after $v_i$ became labeled, so the edge must be in $M$. Now $v_i$ cannot be labeled $(S,0)$, so $v_i$ became labeled because it is connected to some labeled $w_k$ by an edge of $M$. But now the two edges $\{v_i,w_j\}$ and $\{v_i,w_k\}$ are in $M$, a contradiction. So $S$ is a vertex cover.
We know that $|M|\le |S|$, so it suffices to show $|S|\le |M|$, which we can do by finding an injection from $S$ to $M$. Suppose that $w_i\in S$, so $w_i$ is labeled. Since the algorithm failed, $w_i$ is incident with an edge $e$ of $M$; let $f(w_i)=e$. If $v_i\in S$, $v_i$ is unlabeled; if $v_i$ were not incident with any edge of $M$, then $v_i$ would be labeled $(S,0)$, so $v_i$ is incident with an edge $e$ of $M$; let $f(v_i)=e$. Since $G$ is bipartite, it is not possible that $f(w_i)=f(w_j)$ or $f(v_i)=f(v_j)$. If $f(w_i)=f(v_j)$, then $w_i$ and $v_j$ are joined by an edge of $M$, and the algorithm would have labeled $v_j$. Hence, $f$ is an injection. $\qed$
We have now proved this theorem:
Theorem 4.5.6 In a bipartite graph $G$, the size of a maximum matching is the same as the size of a minimum vertex cover. $\qed$
It is clear that the size of a maximum sdr is the same as the size of a maximum matching in the associated bipartite graph $G$. It is not too difficult to see directly that the size of a minimum vertex cover in $G$ is the minimum value of $f(n,i_1,i_2,\ldots,i_k)=n-k+|\bigcup_{j=1}^k A_{i_j}|$. Thus, if the size of a maximum matching is equal to the size of a minimum cover, then the size of a maximum sdr is equal to the minimum value of $n-k+|\bigcup_{j=1}^k A_{i_j}|$, and conversely. More concisely, theorem 4.5.6 is true if and only if theorem 4.2.1 is true.
More generally, in the schematic of figure 4.5.6, if any three of the relationships are known to be true, so is the fourth. In fact, we have proved all but the bottom equality, so we know it is true as well.
$$\matrix{ \hbox{max sdr}&\hbox{$=$?}&\hbox{max matching}\cr \hbox{$\ds\Vert$?}&&\hbox{$\ds\Vert$?}\cr \hbox{min $f(n,\ldots)$}&\hbox{$=$?}&\hbox{min cover}\cr} $$
Finally, note that we now have both a more efficient way to compute the size of a maximum sdr and a way to find the actual representatives: convert the sdr problem to the graph problem, find a maximum matching, and interpret the matching as an sdr.
Exercises 4.5
Ex 4.5.1 In this bipartite graph, find a maximum matching and a minimum vertex cover using the algorithm of this section. Start with the matching shown in red. Copies of this graph are available in this pdf file.
Ex 4.5.2 Show directly that that the size of a minimum vertex cover in $G$ is the minimum value of $n-k+|\bigcup_{j=1}^k A_{i_j}|$, as mentioned above.