How to convert SPOJ Quest4 to Minimum Vertex Cover

Question

The following is a Maximum Bipartite matching problem : http://www.spoj.com/problems/QUEST4/ Through forums i came to know that the problem can be converted into a Minimum Vertex Cover problem, which in turn can be solved by Maximum Bipartite Matching. However, I do not understand how the problem has been converted into Minimum Vertex Cover. Please help me understand this.

Answer 1

Let C , R be the set of all rows and all columns. Now let G be a bipartite graph having edges between C and R where there is an edge (i,j) from C to R if there is a hole in ith row and jth column.

Now consider the vertex cover of this graph. The vertex cover of a graph is a minimal set of nodes such that all edges are covered(each edge is incident upon at least one vertex in the vertex cover).

In our problem graph, each edge represents a hole. Vertices represent rows or columns. Objective- minimize blocks while covering all holes
which is equivalent to -
minimize vertices while covering all edges.