  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-\varepsilon})$-factor for any
$\varepsilon > 0$.
