What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero? 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 &amp; 1 &amp; 0 \\
    0 &amp; 0 &amp; 0 \\
    1 &amp; 0 &amp; 1
  \end{pmatrix}$

the answer is two. For this example

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

the answer is two not three.

Any help to go for head start is appreciated.
Hint: Reduce to bipartite vertex cover, which can be solved efficiently.