Minimal set of rows and columns covering all non-zero entries in matrix

Question

Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns in $I$.

What I have tried

1. Create an intermediate column (between $s$ and $t$) for every column and row.

2. For every column, draw an edge from that column to $t$ with a capacity equal to the number of $1$s it has in it.

3. For every row, draw an edge from that row to $t$ with a capacity equal to the number of $1$s it has in it.

4. Take the cut between this intermediate column and $t$, calculate the entry with the most capacity, add that to set $I$.

5. For the selected row or column, remove all $1$s from that column and recalculate the network flow.

6. Continue to do this until the flow is $0$, i.e., all $1$s have been accounted for.

Examples

1 1 0
1 0 0 
1 0 0 

We would take column 1, and row 1 here.

1 1 1
0 0 0 
0 0 0

We would take row 1 here.

Is there a better approach?

Answer 1

Your problem can be phrased as minimum vertex cover in a bipartite graph: there is a vertex for each row and column, and each non-zero entry contributes an edge. You can find a minimum vertex cover by finding a maximum matching; see Kőnig's theorem.