The Google Hash Code 2015 Test Round (problem statement) asked about the following problem:
- input: a grid $M$ with some marked squares, a threshold $T \in \mathbb{N}$, a maximal area $A \in \mathbb{N}$
- output: the largest possible total area of a set of disjoint rectangles with integer coordinates in $M$ such that each rectangle includes at least $T$ marked squares and each rectangle has area at most $A$.
In Google's terminology, the grid is a pizza, the marked squares are ham, and the disjoint rectangles are slices.
We can clearly rephrase this problem to a decision problem by adding an additional input $n \in \mathbb{N}$ and let the answer be "is there a set of disjoint rectangles satisfying the conditions whose total area is at least $n$ squares".
My question: while the Google problem asked candidates to find a solution which is "as good as possible" for the computation problem on a specific instance, I think it is likely that the general problem (in its decision phrasing) is NP-complete. However, I cannot find a reduction to show NP-hardness. (NP-membership is immediate.) How to prove that this problem is NP-hard?
A few examples follow, to help visualize the problem. Consider the $4$ by $4$ grid $\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$, with marked squares $(1, 1)$, $(0, 2)$ and $(2, 2)$, represented graphically with X
to indicate marked squares:
..X.
.X..
..X.
....
Set $A = 6$ (rectangles of at most $6$ squares) and $T = 1$ (at least one marked square per rectangle), an optimal solution (that covers the entire grid) is to take the following rectangles:
aaAa
bBcc
bbCc
bbcc
On the following grid, with $A = 3$ and $T = 2$:
XXX
.X.
...
One cannot do better than covering only three squares:
AAA
.X.
...
or
XBX
.B.
.b.
(remember that rectangles in the partition cannot overlap).
With other people looking at this question, we tried reductions from bin packing, covering problems, 3-SAT, and Hamiltonian cycles, and we didn't manage to get one to work.