How can I find the minimum number of lines to cover all zeros in a matrix?

Question

I’m working on a problem where I have an n x n matrix, and I need to determine the smallest number of lines (both horizontal and vertical) that cover all the zeros in the matrix. Essentially, I want to find an optimal way to assign these lines to minimize the total coverage.

Here is an Example:

(0, 1, 0, 1, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 0, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 1, 0)

The solution musst be:

(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)

in that case the min number of lines are 4.

is there any olgorithm to solve it?

I tried to create an 2d array, where i could see the sum of zeros in a line and coulm.

The Array for the Example above:

{ 
  [0, 1, 2, 5, 1, 1]
  [2, 0, 0, 0, 0, 0]
  [1, 0, 0, 0, 0, 0]
  [3, 0, 0, 0, 0, 0]
  [1, 0, 0, 0, 0, 0]
  [3, 0, 0, 0, 0, 0]
}

and in my Algorithm i picked the biggest one on the Array and covered the line (set them to false) so i dont have acces on them again. And added 1 to Linelength. But it doesent work for longer lines and coulmns.

After covering the coulmn with the larges number:

{ 
  [0, 1, 2, 0, 1, 1]
  [1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0]
  [2, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0]
  [2, 0, 0, 0, 0, 0]
}

Answer 1

Imagine bipartite graph, where left part contains column numbers Xi, right part contains row numbers Yi, and every zero from matrix defines an edge between corresponding row and column.

Kőnig theorem says that maximum matching (blue edges) is equal to minimum vertex cover (red columns or rows), so every edge (zero in matrix) - both blue and gray - is covered by some red vertex (column or row).

So apply any suitable implementation of maximum bipartite matching algorithm (like maximum_matching in Python networkx library)

Answer 2

It can also be formulated as an integer linear program.

Let:

• h_i equal 1 if a line covers row i and equals 0 otherwise; and
• v_j equal 1 if a line covers column j and equals 0 otherwise.

Then the formulation is:

min Σ_ih_i + Σ_jv_j

subject to:

h_i + v_j >= 1 for all i,j for which the element at row i, column j is a zero.

All variables can equal zero or one only.