Biggest non-contiguous submatrix with all ones

user_2598977 0
Viewed 113

I'm tackling the problem of finding a non-contiguous submatrix of a boolean matrix with maximum size such that all of its cells are ones.

As an example, consider the following matrix:

M = [[1, 0, 1, 1],
     [0, 0, 1, 0],
     [1, 1, 1, 1]]

A non-contiguous submatrix of M is specified as a set of rows R and a set of columns C. The submatrix is formed by all the cells that are in some row in R and in some column in C (the intersections of R and C). Note that a non-contiguous submatrix is a generalization of a submatrix, so any (contiguous) submatrix is also a non-contiguous submatrix.

There is one maximum non-contiguous submatrix of M that has a one in all of its cells. This submatrix is defined as R={1, 3, 4} and C={1, 3}, which yields:

M[1, 2, 4][1, 3] = [[1, 1, 1],
                    [1, 1, 1]]

I'm having difficulties finding existing literature about this problem. I'm looking for efficient algorithms that don't necessarily need to be optimal (so I can relax the problem to finding maximal size submatrices). Of course, this can be modeled with integer linear programming, but I want to consider other alternatives.

In particular, I want to know if this problem is already known and covered by the literature, and I want to know if my definition of non-contiguous matrix makes sense and whether already exists a different name for them.

Thanks!

linear-programming matrix boolean optimization algorithm
1 Answers

Since per your response to Josef Wittmann's comment you want to find the Rectangle Covering Number, my suggestion would be to construct the Lovász–Saks graph and apply a graph coloring algorithm.

The Lovász–Saks graph has a vertex for each 1 entry in the matrix and an edge between each pair of vertices whose 2x2 matrix contains a zero. In your example,

[[1, 0, 1, 1],
 [0, 0, 1, 0],
 [1, 1, 1, 1]]

we can label the 1s with letters:

[[a, 0, b, c],
 [0, 0, d, 0],
 [e, f, g, h]]

and then get edges

a--d, a--f, b--f, c--d, c--f, d--e, d--f, d--h.

a b   a 0   0 b   b c   0 c   0 d   0 d   d 0
0 d   e f   f g   d 0   f h   e f   f g   g h

I think an optimal coloring is

{a, b, c, e, g, h} -> 1
{d} -> 2
{f} -> 3.
user_21446690
Related