I wonder about the following decision problem :

Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$.

Question: is it possible to cover all the ones of the matrix with $N$ squares of side length $k$?

It is possible that the squares cover some of the zeros in the matrix, and they can overlap with each other.

I get the impression that it is $\textsf{NP}$-complete (it is clearly $\textsf{NP}$), I find some similarities with Grid covering by rectangles but can't find a good reduction.

Might I get some insight on the problem?


EDIT: After days of reflexion, these are the ideas I've got:

I try to create a reduction from a Satisfiability problem with the following approach.

Given $\varphi = \bigwedge\limits_{i=1}^m C_i$ where $\forall i \in [\![1,m]\!]$, $C_i = (\ell_{i1}\vee \ell_{i2}\vee\ell_{i3})$ and $\ell_{ij}$ is either $x$ or $\neg x$ where $x\in\mathcal{V} = \{x_1,…,x_n\}$. I create the matrix $A$ with dimensions $(2m+2)\times (6n-1)$ defined by:

  • $\forall j \in [\![1,n]\!], a_{1,6(j-1)+3} = a_{2m+2,6(j-1)+3} = 1$;
  • $\forall i,j\in [\![1,m]\!]\times [\![1,n]\!]$, for $k = 2i - 1$ and $k = 2i$ and for $p = 6(j-1) +2$, $p = 6(j-1) + 3$ and $p = 6(j-1) + 4$, $a_{kp} = 1$;
  • all other coefficients are set to 0.

Here's a visual representation of the matrix:

matrix construction

With this matrix, if, for a variable $j$, we allow the use of $2m-1$ squares of size $2\times 2$, we can either cover all of (except extremities) the column $6(j-1)+1$ or the column $6(j-1) + 5$, but not both and not a mix between them. This can simulate a boolean variable!

The idea I got then was to put ones in the column $6(j-1)+1$ save if $x_j$ appears in the clause $C_i$ in which case, $a_{2i-1, 6(j-1)+1}$ and $a_{2i,6(j-1)+1}$ stay to zero (and do the same thing similarly in the column $6(j-1)+5$ with the $\neg x$ litteral).

If we then allow the use of $2n-1$ squares for each clause $C_i$, we need one of the variables to be set correctly in the clause to cover all ones in lines $2i-1$ and $2i$. The problem with this reduction is that you can "gain" some squares in a clause with multiples variables set correctly to change the disposition of a variable elsewhere.

My second idea was to create a reduction from $\texttt{ONE-IN-THREE-SAT}$, in which we ask if there is an assignation to $\varphi$ which satisfies exactly one litteral per clause, or even its restriction where we can suppose that $\varphi$ contains no negations, but I couldn't find something satisfying, so I'd like some help again!


Your Answer

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

Browse other questions tagged or ask your own question.