On the Exact Complexity of Polyomino Packing

摘要

We show that the problem of deciding whether a collection of polyominoes, each fitting in a 2 x O(log n) rectangle, can be packed into a 3 x n box does not admit a 2^{o(n/log{n})}-time algorithm, unless the Exponential Time Hypothesis fails. We also give an algorithm that attains this lower bound, solving any instance of polyomino packing with total area n in 2^{O(n/log{n})} time. This establishes a tight bound on the complexity of Polyomino Packing, even in a very restricted case. In contrast, for a 2 x n box, we show that the problem can be solved in strongly subexponential time.