15
$\begingroup$

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.

Visual example of the problem

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.

$\endgroup$
  • 3
    $\begingroup$ Hint: Look for a reduction from Vertex Cover, in which we create an $|E|$ by $|V|$ grid of blocks, each of which is a 3 by 3 block of matrix elements. Each row of blocks corresponds to an edge, and will contain 2 specially designed blocks corresponding to its endpoint vertices. For each vertex there will be a height-$3|E|$, width-1 rectangle that passes through the centre column of the column of 3-by-3 blocks corresponding to that vertex. How can you force the total of any valid $k$-vertex cover to cost exactly $|E|(|V|+3)+k$? (You will need other rectangles.) $\endgroup$ – j_random_hacker Jul 11 '17 at 7:40
  • $\begingroup$ I think this is probably a homework exercise, so I'm a bit reluctant to say much more than that for now. The cost formula I gave has a some clues in it. Keep in mind that you can force at least 1 of several rectangles by making them the only rectangles that cover some matrix element (the special case of 1 rectangle is also useful). FWIW, I also tried using a $|V|$-by-$|V|$ grid first, where choosing a vertex would correspond to "crossing out" a row and corresponding column, but couldn't figure out how to force the $i$-th column to be chosen when the $i$-th row is chosen or vice versa. $\endgroup$ – j_random_hacker Jul 11 '17 at 18:09
  • $\begingroup$ I had the same problem with $|V|$-by-$|V|$ grid. I think I see what kind of solution you have in mind (I don't have exactly the same cost formula though), see my edit. By the way, it's not a homework exercise. It's a combinatorial problem that appeared in a real life engineering problem. We solve it with MIP, but I wanted to be sure the problem was NP (and had no polynomial solution). In any case, if you confirm the solution is valid, you can put your hint as an answer and I will validate it (since I found the solution with your help). $\endgroup$ – Yann Jul 11 '17 at 23:08
  • 1
    $\begingroup$ Yes, that's almost exactly the reduction I had in mind! :) I made your "type 4" rectangles slightly longer at one end: where yours occupy 2 cells within a block, mine occupy all 3. Instead of special "type 3" rectangles for the endblocks, I use the entire top row, just like "type 2" rectangles for $a < j < b$. Finally I have a rectangle occupying the centre-left and bottom-left cells within each left endblock (horizontally flipped for each right endblock). So you can cover the bottom 2 rows of all blocks including and between endblocks using a |= or =| pattern. $\endgroup$ – j_random_hacker Jul 12 '17 at 11:51
  • 1
    $\begingroup$ I like your $|E|$-by-$3|V|$ reduction idea. With this, unlike with the $3|E|$-by-$3|V|$ reduction, there can be minimum-cost solutions that do not correspond to vertex covers -- but all such solutions can be turned into equal(ly minimum)-cost solutions using the same argument as in your last bullet point, so this isn't a problem for the reduction :) $\endgroup$ – j_random_hacker Jul 12 '17 at 11:54
4
$\begingroup$

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)

enter image description here

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<a$ or $b<j$, this is a 3-by-3 rectangle covering the entire block.
  • 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<j<b$, this is a 1-by-3 rectangle covering the top row of the block.

So we have $|E||V|$ rectangles of type 2, those rectangles will be obligatory to choose, as each will be the only cover for the top-left (or top-right) corner of the block it's in.

As we have said, each edge correspond to a row, with two blocks (let's call them endblocks) corresponding to the endpoints of the vertices $(e_i,v_a)$ and $(e_i,v_b)$, now we have rectangles of type 3:

  • for endblock $(e_i,v_a)$ (resp. $(e_i,v_b)$), we have a 1-by-2 rectangle covering the top-right (resp. top-left) corner of the endblock.

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$

$\endgroup$

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.