# 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!

• Welcome :) In case you're looking for a reasonable algorithm, I would suggest looking for a roughly balanced vertex separator (e.g., find a width-$k$ horizontal interval such that equal numbers of points are entirely to its left and entirely to its right, then take all points that overlap its horizontal extent), and for each possible way of covering these points, solve (and maybe memoise) the left-problem and right-problem independently. Feb 21 at 14:35