# Matrix covering by squares

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?

Thanks.

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:

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!