All twelve pentominoes can be obtained by attaching a single unit square (edge to edge) to one of the squares that make up one (or more) of the following four tetrominoes:
a) What is the least number of pentominoes required so that all 35 hexominoes can be obtained by attaching (edge to edge) a single square to one of the squares that make up one (or more) of those chosen pentominoes?
b) What about the least number of hexominoes in order to obtain in a similar way all 108 heptominoes?
You can solve this set covering problem via integer linear programming as follows. Let $P$ be the set of larger polyominoes, let $Q$ be the set of smaller polyominoes, and for $p\in P$ let $Q_p \subset Q$ be the polyominoes that can construct $p$ by adding a cell. For $q\in Q$, let binary decision variable $x_q$ indicate whether $q$ is selected. The problem is to minimize $\sum_{q\in Q} x_q$ subject to linear constraints $$\sum_{q\in Q_p} x_q \ge 1 \quad \text{for all $p\in P$}$$ that enforce that each larger polyomino can be constructed from some selected $q$.
The minimum for part a is
8, with the following free pentominoes:
{(1,1),(2,1),(2,2),(2,3),(3,2)}
{(1,1),(2,1),(2,2),(3,2),(3,3)}
{(1,1),(2,1),(2,2),(3,2),(4,2)}
{(1,1),(2,1),(2,2),(3,1),(3,2)}
{(1,1),(1,2),(1,3),(2,2),(3,2)}
{(1,1),(1,2),(2,2),(3,2),(4,2)}
{(1,1),(1,2),(1,3),(2,1),(3,1)}
{(1,1),(2,1),(3,1),(4,1),(5,1)}
If I have constructed the sets correctly, the minimum for part b is
19, with the following free hexominoes:
{(1,5),(2,1),(2,2),(2,3),(2,4),(2,5)}
{(1,4),(1,5),(2,1),(2,2),(2,3),(2,4)}
{(1,1),(2,1),(2,3),(3,1),(3,2),(3,3)}
{(1,1),(2,1),(2,2),(2,3),(3,1),(3,3)}
{(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)}
{(1,1),(2,1),(2,2),(2,3),(3,3),(4,3)}
{(1,3),(2,2),(2,3),(3,1),(3,2),(4,1)}
{(1,3),(2,1),(2,2),(2,3),(3,3),(3,4)}
{(1,3),(2,2),(2,3),(2,4),(3,1),(3,2)}
{(1,2),(2,1),(2,2),(2,3),(2,4),(3,4)}
{(1,3),(2,3),(3,2),(3,3),(4,1),(4,2)}
{(1,3),(2,1),(2,2),(2,3),(3,3),(4,3)}
{(1,3),(2,1),(2,2),(2,3),(2,4),(2,5)}
{(1,3),(2,3),(3,3),(4,1),(4,2),(4,3)}
{(1,4),(2,1),(2,2),(2,3),(2,4),(3,4)}
{(1,2),(1,4),(2,1),(2,2),(2,3),(2,4)}
{(1,2),(2,1),(2,2),(2,3),(3,1),(3,2)}
{(1,1),(1,2),(1,3),(2,1),(2,3),(2,4)}
{(1,1),(2,1),(3,1),(4,1),(5,1),(6,1)}
Let us start by considering this hexomino:
It is clear that there is only one pentomino that can be extended to this:
And since we have to use that pentomino, we can tick off several hexominoes that can be made from it:
Now consider this set of hexominoes:
The only way to make these from a pentomino is to add one of its extremal squares, and in each case this gives the single pentomino it can be made from: W, N and L, respectively. We add these to our set and tick off each hexomino that can be made from them.
So far, so good. Sadly, no more hexominoes have a unique requirement. Let's label them with all the pentominoes they can be made from:
We can note that we need P or Y, P or U, F or Y and F or U, and that these four requirements can be simplified to (P and F) or (U and Y). Looking at each of these pairs, we see there is no single other pentomino that provides a complete covering, but there are several pairs of other pentominoes that do so. Thus our minimal covering set is 8, for example:
