1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.