Question

A vertex cover of an undirected graph G = (V,E) is a subset of the vertices which touches every edge—that is, a subset $\mathit{S}\mathbf{\subset }\mathit{V}$such that for each edge $\left\{U,V\right\}\mathbf{\in }\mathit{E}$, one or both of u, v are in S. Show that the problem of finding the minimum vertex cover in a bipartite graph reduces to maximum flow. (Hint: Can you relate this problem to the minimum cut in an appropriate network?)

Short answer

Allow the edges next to or to have capacity 1 and the original edges to have capacity unlimited.

Step-by-step solution

The bi-partition of the graph G:

Let’s L R be the graph G' bi-partition.

Add a phony source node s containing edges flowing out with every vertex of L and a dummy target node t with edges coming in from every vertex of R to make a network G'. The remaining original edges should be directed from L to R. Allow the edges next to s or t to have capacity 1 and the original edges to have capacity unlimited. Consider any$\left(s,t\right)-cut\left(S,\left(\overline{S}\right)\right)\left(s\in S\right)$ in this network which has sizeless than$\infty$.

Representing the pair of Edges

Let E_S represent the set of edges that cross the cut $Sto\overline{S}$. So, that all $e\in ES$, e seems to be a result either of s or t (otherwise the cut contains an infinite capacity edge).

Suppose C be the collection of all vertices coincident to edges in E except and. Therefore C is indeed a vertex cover of G; if it isn't, then there is some sort of problem. $\left\{u,v\right\}\in Eforu,\in L,v\in Rwithu,v\in C$, so no edge on the path s - u - v t crosses the cut, a contradiction.

Note $\left|C\right|=\left|E_s\right|$his determines the cut's size $\left(S,\overline{\left(S\right)}\right)$.

On the other hand, let C be a vertex cover of G'. Assume following E_s crossing collection of edges. Let$S\subset V$ Any pair of vertices in L that aren't in C, and the set of vertices in R that aren't in C and s.

(s,t) cut from S to $\overline{S}$.

First, suppose that E_s contains an infinite capacity edge e = (u,s) . Since $u\in S,u\notin C$but then since $v\in S,v\notin C$, and so C does not cover^e. Hence E_s contains only edges with capacity 1. Moreover, $\left|E\_s\right|=\left|L\cap C\right|+\left|R\cap C\right|=\left|C\right|$and so the size of the cut, $\overline{S}is\left|C\right|$.

Conclusion

Let $\left(s,\left(\overline{s}\right)\right)$ be a minimum cut in G₀. Then C obtained as above is a minimum vertex cover of G: suppose not; then there is a smaller vertex cover C' of G, but then there is a smaller cut $S\text{'},\left(\overline{S\text{'}}\right)inG\text{'}$.