Inapproximability of the Smallest Superpolyomino Problem

الأصل · EN

We consider the smallest superpolyomino problem: given a set of colored polyominoes, find the smallest polyomino containing each input polyomino as a subshape. This problem is shown to be NP-hard, even when restricted to a set of polyominoes using a single common color. Moreover, for sets of polyominoes using two or more colors, the problem is shown to be NP-hard to approximate within a O(n¹/³⁻ε)-factor for any ε > 0.