Show this 2D Grid Set Cover-ish problem is NP-Complete?

Question

Given a $n \times m$ rectangular grid of cells each with an integral weight: $w_{i,j}$ and two integer parameters $w \ge 2$ and $h \ge 2$ (for group width and height respectively). Select the subset of cells that maximizes the combined weight of the selected cells and is constrained such that each selected cell is a part of at least one fully selected 'group' of size $w \times h$.

For example, if in the following 5x5 grid of weights we are required to select 2x2 groups of cells ($n = m = 5, w = h = 2$) We can use the selection on the right to get the maximum value of 13.

This specific small example hides a bit of the complexity of the problem which arises when individual 'groups' need to work together to overcome negative weights in their overlap, and when $w$ and $h$ are larger.

How can I show that the decision problem variant of this optimization problem is NP-Complete? Is it possible when $w = h = 2$ or do they have to be larger?

---

This problem can be cast as a straightforward integer programming problem. For example using an auxiliary variable on each group (there would be $n-w+1 \times m-h+1$ of these auxiliary variables), and having two sets of constraints first saying that each group can only be selected if all of its constituent cells are selected and secondly saying that each cell can be selected if at least one of its containing groups is selected. This is of course not really relevant to showing the problem is NP-complete though.

This does seem very similar to a set cover-ish problem and I've tried from that angle for a bit with no success. The part that I've struggled with is the restriction on the sets themselves how they consist of overlapping areas. If the 'groups' were arbitrary (not rectangular) then it is much easier to show as NP-complete.

I have played a little bit with a dynamic programming solution (which could disprove that it is NP-complete!), but I was only able to get that to work for the one dimensional case.

I am also interested in any references to problems like this.

Answer 1

A straightforward reduction follows from Fowler, Paterson, and Tanimoto "Optimal packing and covering in the plane are np-complete" 1981.

The details are in the paper. Summarized: To transform 3-SAT into this problem fill a large grid with negative values, then place large positive valued cells in specific locations. Using $w=h=3$ we can create a situation where the positive valued cells create 'loops' of even numbered cells which correspond to literals. The clauses correspond to specific cells which will be covered by one of the loops if satisfied, or else require an additional 3x3 area to be selected if not satisfied (thereby reducing the total value). In fact, an efficient algorithm for this particular problem would identify not only if a satisfying result existed for any 3-SAT instance - but also the 'most satisfying' result.