Inapproximability of the Smallest Superpolyomino Problem

Abstract

We consider the \emph{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^{1/3-\epsilon })$-factor for any $\epsilon >0$.

An abstract version has been submitted to Fall Workshop on Computational Geometry 2012