What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Question

Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero one at a time what will be minimum number of operations (i.e multiplications) I will need. For example, for the matrix

$\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}$

the answer is two. For this example

$\begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$

the answer is two not three.

Any help to go for head start is appreciated.

Answer 1

Hint: Reduce to bipartite vertex cover, which can be solved efficiently.