Minimum Vertex Cover in Bipartite Graphs

There’s no known polynomial time algorithm for finding a minimum vertex cover in a general graph. However, when it comes to finding a minimum vertex cover in bipartite graphs, once again, the Ford-Fulkerson algorithm comes to the rescue.

In this lesson, we see exactly how to do this. But first, we want to make the following assumption about residual networks in the hope that it will make the exposition easier to understand:

This assumption greatly simplifies the illustrations as well as the proofs. For instance, instead of using a convoluted expression like “reachable from $s$ using only edges with non-zero capacity,” we can simply say “reachable from $s$.”

The basic idea

The Ford-Fulkerson algorithm can be used for finding a minimum vertex cover in bipartite graphs. To do this, a flow network $F$ is created against a given bipartite graph $G$ having partite sets $L$ and $R$. This is done in exactly the same way as was seen for the problem of finding a maximum matching:

After the Ford-Fulkerson algorithm is run to completion on $F$, there is no augmenting path in its corresponding residual network. If $V_s$ is the set of vertices in the residual network reachable from $s$, and $V_t$ consists of the remaining vertices, then the edges in the flow network from $V_s$ to $V_t$ form a minimum cut $\langle V_s, V_t\rangle$. Vertices in $V_s$ and $V_t$ can be carefully picked to form a minimum vertex cover $K$ as follows:

$$K = (L\cap V_t) \cup (R \cap V_s)$$

We’ll see in a bit why this forms a minimum vertex cover.

Example

Consider the flow network on the left side of the illustration below, built from a bipartite graph. Using the Ford-Fulkerson algorithm on the flow network, a maximum matching of size $3$ can be found in the original bipartite graph, corresponding to the edges from $L$ to $R$ with unit flow. Such a matching would leave the vertices $v_4$ and $v_8$ unmatched.

The residual network corresponding to the flow network is shown on the right in the illustration below. Notice how when there is unit flow on an edge in the flow network, the direction of the corresponding edge in the residual network reverses. However, if there is no flow in an edge of the flow network, the direction of the corresponding edge in the residual network remains unchanged.

In the residual network, the vertices in $V_s$ that are reachable from the source $s$ are highlighted in red, and all other vertices that are in $V_t$ ...