- 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.
Asked By : a3nm
Answered By : Vor
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:
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. 
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. 
Finally we can build shift and turn gadgets to carry the signals according to the underlying planar graph and adjust the endpoints: 
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. Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48775
