2
$\begingroup$

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.

Example problem with solution

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.

$\endgroup$
2
  • $\begingroup$ Is the selected group of cells required to be connected? If so you can probably reduce from rectilinear Steiner tree, where terminals have large positive weights and the other cells have negative weights with a small absolute value. Tthis should work for any fixed choice of $w$ and $h$. (As a pedantic note: the problem as formulated cannot be NP-complete as it is not in NP because it is not a decision problem). $\endgroup$
    – Steven
    Commented Aug 30, 2022 at 22:49
  • $\begingroup$ Thank you - I updated the problem to clarify that I'm interested in the decision problem variant of this optimization problem. The final output set of cells is not required to be connected. Each group itself is connected (as it is a rectangle). Thank you for the pointer to the rectilinear Steiner tree regardless, I will see where that takes me! $\endgroup$
    – Matt D
    Commented Aug 30, 2022 at 23:12

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.