[Math] Is packing rectangles exactly into a larger rectangle NP-complete

combinatorial-geometrynp-completepacking-problemrectangles

I want to pack a number of rectangles into a larger rectangle, however, unlike other questions that I could find, I would like to do so exactly, without allowing any wastage.
I do not really care whether 90° rotation is allowed, or not.

I find it hard to construct a reduction from the 2D-bin-packing problem to this problem, since this very special, restricted case of fitting the rectangles exactly might be more easy to decide after all. Any other reductions or proofs that I could find lead me to the same doubts. I also failed to construct a correct reduction from the 2d-knapsack problem with a similar argument.

My stomach tells me that this simplified problem is still NP-complete, but I was not able to find any proofs and I would be happy to be pointed to the correct direction. Additionally, if the constraint is changed so that only equal sized smaller rectangles allowed, is the problem still NP-complete?

Best Answer

Partition can be reduced to this problem. Set $S$ can be partitioned iff set of rectangles $\{1 \times (4\cdot x)| x \in S\}$ can be packed into rectangle $2 \times (\sum_{x \in S} 2x)$: rectangles from upper row corresponds to one subset, from bottom to other, and multiplication by $4$ ensures all rectangles are placed horizontally.

Related Question