6
$\begingroup$

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:

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!

$\endgroup$
2
$\begingroup$

This was proved NP-complete in "Optimal Packing and Covering in the Plane are NP-complete" (Fowler, Paterson and Tanimoto, Information Processing Letters 1981). I found a freely available version of the paper here. They give a neat reduction from 3SAT -- I'll summarise this below, but the paper is short and easy-to-read with several diagrams, and I recommend reading it!

For each variable they construct a "loop of wire" having an even number of points (1-cells in your formulation), and such that a single square can cover two adjacent points in the loop but no more. This means that there are two ways to cover all points in the loop using a minimal number of squares: Either use a square to cover points 1 and 2, another square to cover points 3 and 4, and so on, or use a square to cover points 2 and 3, another square to a cover points 4 and 5, and so on. Which minimal cover is used corresponds to whether the variable is assigned a value of true or false.

For each clause, they add a single extra point out to the right, and "extrude" the wire loops for the three relevant literals near this point. If any of them is in the right state, the extra point for this clause can be covered "for free" by a square in that loop. Negated literals are achieved simply by slightly compressing a few links in the loop, so that at a position to the right of the compression zone the "parity" of the wire is reversed.

In order to thread the loops through each clause they participate in, wires need to be able to cross over with their signals remaining independent. Interestingly, this "just works" without any additional gadgets.

$\endgroup$
2
  • $\begingroup$ Thank you so much! I'm glad this is close to the ideas I first had. $\endgroup$ – Nathaniel Feb 21 at 14:21
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Feb 21 at 14:35

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.