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.

up vote 10 down vote accepted

This is a sketch of a reduction from MONOTONE CUBIC PLANAR 1-3 SAT :

Definition [1-3 SAT problem]:
Input: A 3-CNF formula $\varphi = C_1 \land C_2 \land ... \land C_m$, in which every clause $C_j$ contains exactly three literals: $C_j = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$.
Question: Does there exist a satisfying assignment for $\varphi$ such that each clause $C_j$ contains exactly one true literal.

The problem remains NP-complete even if all literals in the clauses are positive (MONOTONE), if the graph built connecting clauses with variables is planar (PLANAR) and every variable is contained in exactly 3 clauses (CUBIC) (C. Moore and J. M. Robson, Hard tiling problems with simple tiles, Discrete Comput. Geom. 26 (2001), 573-590.).

We use $T=3, A=6$, and in the figures ham is represented with blue boxes (transgenic ham?), pizza with orange boxes.

The idea is to use tracks of ham that carry positive or negative signals; the track is made with an alternation of 1 and 2 pieces of hams placed far enough so that they can be covered exactly by one slice of pizza of area $A$; the segments of the track are marked alternately with $+$ or $-$, the track will carry a positive signal if slices are cut on the positive segments:

enter image description here

Each variable $x_i$, which is connected to exactly 3 SAT clauses, is represented by three adjacent endpoints of three ham tracks (positive segment), in such a way that there are 2 distinct ways to cut it, one will "generate" a positive signal on all 3 tracks (it reppresent the $x_i = TRUE$ assignment) the other a negative signal ($x_i = FALSE$). Notice that we can also generate mixed positive and negative signals, but in that case at least one ham remains uncovered.

enter image description here

Each clause $C_j$ of the 1-3 SAT formula with 3 literals $L_{i,1}, L_{i,2}, L_{i,3}$ is simply represented by a single ham with three incoming positive segments of three distinct ham tracks; by construction only one of the three tracks carrying a positive signal can "cover" the ham-clause.

enter image description here

Finally we can build shift and turn gadgets to carry the signals according to the underlying planar graph and adjust the endpoints:

enter image description here

Suppose that the resulting graph contains $H$ hams. By construction every slice of pizza must contain exactly 3 hams, and in all cases every slice can be enlarged up to area $A$.

If the original 1-3 SAT formula is satisfiable then by construction we can cut $H /3$ pieces of pizza (with total area of $A H / 3$) and no ham remains uncovered.

On the oppposite direction, if we can cut $H /3$ pieces of pizza (with total area $A H / 3$) then no ham remains uncovered, and the signals on the variables gadgets and on the clauses are consistent: the ham on the clause is covered by exactly one positive slice coming from a positive variable, and every variable generates 3 positive signals or 3 negative signals (no mixed signals); so the cuts induce a valid 1-3 SAT assignment.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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