Reduce Subset Sum to Polyomino Packing

Question

This is a homework assignment, so any help is appreciated.

I should prove that the following problem is NP-complete. The hint says that you should reduce the subset sum problem to this problem.

Given a set of shapes, like the below, and an m-by-n board, decide whether is it possible to cover the board fully with all the shapes. Note that the shapes may not rotate.

For example, for a 3-by-5 board and the following pieces, the board can be covered like this:

Now the important thing to note is that the subset sum problem we are trying to reduce should be given input length polynomial in terms of m and n.

Any ideas for using another NP-complete problem are appreciated.

Answer 1

The easiest reduction is from the partition problem.

Suppose that we have a set of positive numbers that sum to 2n and we want to know a subset of them sums to n.

We create a set of blocks of length the numbers and width 1, then try to fit them into a rectangle of width 2 and length n. We can succeed if and only if the partition problem was solvable for those numbers, and the rows are the partition. So any partition problem can be reduced to a polyomino packing problem in linear time. Since the partition problem is NP-complete, we are done.

But they said subset sum. If they mean subset sum on positive numbers, then we can just use another trick. Suppose that our numbers sum to n and we want to know if a subset sums to k. Then we just add 2 numbers to the problem of size k+1 and size n-k+1 and aim to solve the partition problem. If we succeed, our additional 2 numbers couldn't have been in the same partition and so the rest are a solution to the partition problem. Since we've already reduced the partition problem to polyomino packing problem, we are done.

If they intended subset sum from numbers that can be both positive and negative, then I don't see the reduction that they suggested. But since I've managed to reduce 2 well-known NP-complete problems to this one, I think we're good.