2
$\begingroup$

Given a matrix $M$ of certain size $h\times w$, where $h\leq w$, for example $5\times 6$, are also given the following set $B$ of additional all-ones matrices, that I like to call target (b)oxes.

$$ \begin{matrix} Boxes: & \begin{bmatrix} % 2 x 5 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 3 x 4 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 4 x 3 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 5 x 2 1 & 1\\ 1 & 1\\ 1 & 1\\ 1 & 1\\ 1 & 1 \end{bmatrix}\\ Sizes: & 2 \times w - 1 & 3 \times w - 2 & 4\times w - 3 & 5\times w - 4 \end{matrix} $$

As you can see, these specific boxes have sizes starting from $2\times w - 1$ up to $h\times w - h + 1$.

The problem is finding a submatrix of $M$ that is isomorphic with any of the boxes in $B$. In other words, swapping rows between them, and/or columns between them so that any of the boxes of $B$ can be placed, for example, in the top left corner of $M$.

If there is more than one solution, the box of maximal height must be choosen, and if there's more than one solution of maximal height, then the one with maximal height and width.

The problem has the following properties:

  • $2 \leq h \leq w$.
  • Each row of $M$ has at least one $0$.
  • Deduced from the way $B$ is generated, for each $b\in B$ of size $b_h\times b_w$, it happens that $b_h + b_w - 1 = w$.

Is there a way of solving this problem in polynomial time? Can any technique from lineal algebra or numerical characterization of matrices help to the problem?

$\endgroup$
0
4
$\begingroup$

The problem is NP-hard; it is at least as hard as the biclique problem.

If you can solve the problem for a single shaped box, you can solve for all boxes by just iterating over all the boxes. So your problem reduces to:

Given a matrix $M$ and integers $h', w'$, find a $h'\times w'$ submatrix of $M$ that is all ones, or report that none exists.

This problem is NP-hard. In particular, if we take any undirected bipartite graph $G$ with adjacency matrix $M$, then $M$ has an all-ones $k \times k$ submatrix if and only if $G$ has a $k$-biclique. Testing for the presence of a $k$-biclique is NP-hard, so your problem must be, too.

$\endgroup$
12
  • $\begingroup$ I don't see 100% why both problems are equivalent, becase $M$ is not an adjacency matrix (it's not square or symmetrical). $\endgroup$ – Peregring-lk Sep 9 '20 at 6:37
  • $\begingroup$ Another thing... that I removed in a previous edition (damm myself, I will edit it after work), is that boxes has priorities, so the $5\times 2$ box has priority over $2\times 5$ because height has priority over width, so, could be there a way to take advantage of the knowledge that, if I'm trying an specific box is because we know the previous boxes have all failed? $\endgroup$ – Peregring-lk Sep 9 '20 at 7:14
  • 1
    $\begingroup$ @BernardoSubercaseaux, because a submatrix can pick rows 1,2 and columns 3,4 (say), whereas a clique would require that if you picked rows 1,2 then you pick columns 1,2. $\endgroup$ – D.W. Sep 9 '20 at 16:00
  • 1
    $\begingroup$ @Peregring-lk, the general case of your problem includes the special case of a square box; since the special case is NP-hard, the general case is, too. $\endgroup$ – D.W. Sep 9 '20 at 19:35
  • 2
    $\begingroup$ @Peregring-lk, not in a bipartite graph. $\endgroup$ – D.W. Sep 9 '20 at 20:21

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.