Grid covering by rectangles

We have a $N_1 \times N_2$ grid.
We have a collection of rectangles on this grid, each rectangle can be represented as a $N_1$-by-$N_2$ binary matrix $R$. We want to cover the grid with those rectangles.

Is the decision version of this set cover problem NP-complete ?

• Input : Collection $\mathcal{C}=\{R_1,R_2,\dots,R_L\}$ of rectangles on the grid (input size: $N_1N_2L$), and $K \in \mathbb{N}^+$

• Output : Subset $\mathcal{S}\subset\mathcal{C}$ with $|\mathcal{S}|\leq K$ and $\mathcal{S}$ containing for each cell at least one rectangle covering it.

I found that the 1D case ($N_2=1$) can be solved in polynomial time by dynamic programming: any optimal cover is going to be the union of

• an optimal cover for some subproblem of covering the first $N_1-n_1$ cells.

• a 1D rectangle, i.e. an interval, covering the remaining $n_1$ cells.

I don't think however DP can work for the 2D problem: for the 1D problem, you have a $N_1$ subproblems to solve, but for 2D you have $\binom{N_1+N_2}{N_2}$ subproblems (number of North-East lattice paths on the grid).

I think the problem might be NP, but I am not sure (though it seems harder than P), and I have not succeed in finding a polynomial reduction from an NP-complete problem (3-SAT, Vertex Cover,...)

Any help or hint is welcome.

Thanks to j_random_hacker's hint, I've found a solution to reduce Vertex Cover to the Grid Problem:

We make a $|E|$-by-$|V|$ grid of 3-by-3 blocks, i.e. a $3|E|$-by-$3|V|$ grid, with vertices ordered as columns $\{v_1,\dots,v_{N_1}\}$ and edges ordered as rows $\{e_1,\dots,e_{N_2}\}$.
We'll construct rectangles on this grid (the drawing below will help a lot understanding the different rectangles used)

For each vertex, we create a rectangle of type 1, which covers the central column of the column of blocks corresponding to that vertex, so we have $|V|$ rectangles of type 1.

Each block correspond to a unique couple $(e_i,v_j)$, with $e_i=(v_a,v_b)$ for each block we add a rectangle of type 2 :

• if $j

• if $j=a$ (resp. $j=b$), this is a 3-by-1 rectangle covering of the left (resp. right) column of the block.

• if $a

We have $2|E|$ rectangles of type 3, and again, they're obligatory as each will be the only cover for the top-right corner (if it's the first endblock) or the top-left corner (if it's the second endblock) it's in.

Now, for each edge we construct rectangles of type 4, between the endblocks, we have two rectangles for the second row :

• One going from the central square of the first block to the central-left square of the second block.

• One going from the central-right square of the first block to the central square of the second block.

• And the same two rectangles for the third row.

We have $4|E|$ rectangles of type 4, those are not all obligatory however.

So now, to cover the grid:

• $|E|(|V|+2)$ rectangles (type 2 and 3) are obligatory and $|V|+4|E|$ (type 1 and 4) are optionnal.

To cover, for a given edge, the part between the edge endblocks not yet covered (second and third rows of the row of blocks), we can either use:

• the four rectangle of type 4.

• one rectangle of type 1 and two rectangles of type 4.

Note that in any case, we need at least two rectangles of type 4.

So here the cost function will be : $|E|(|V|+4) + k$

-
If their is a valid vertex cover with less than k vertex: we use the $|E|(|V|+2)$ obligatory rectangles, then for the optionnal rectangles, we can use the rectangles of type 1 corresponding of the vertex cover, and for every row, we need only 2 rectangles of type 4 (we already have a rectangle of type 1). So if the graph has a valid vertex cover, the grid has a valid set cover.

-
If we have a valid set cover for the grid (with less than $|E|(|V|+4) + k$) rectangles, then for each edge, either we already have a rectangle of type 1 (and the edge is "covered") or four rectangle of type 4, in which case, we can replace two of them by one rectangle of type 1, and we still have a valid cover with $|E|(|V|+4) + k$ rectangles. By iterating this process, we reach a valid solution with no row using four rectangle of type 4, from which we can obtain a valid vertex cover.

So the vertex cover can be reduced to the grid cover. And the grid problem instance can be encoded by $|E|(|V|+6) + |V|$ covers on a grid with $9|V||E|$ elements, so the reduction is polynomial and the grid problem is NPC.

PS :
I noticed after writing this answer that a lot of rectangles are actually useless and much simpler reduction can be made using a $|E|$-by-$3|V|$ grid with $|V|+4|E|$ covers, using cost function $3|E|+k$

StackExchange Computer Science Q#77754, answer score: 4