Consider the following problem that I call »Minimum Type Selection«:
- Input: $k$ sets of bit vectors, each of length $n$ and a number $l$.
- Question: Is it possible to pick exactly one bit vector from each of the $k$ sets such that these $k$ bit vectors composed row-wise as a matrix contain at most $l$ distinct columns.
I was able to show that this problem is NP-complete. I now wonder about the parameterized complexity where $k$ is the parameter. For fixed $k$, the problem is trivially in P, implying that the parameterized problem is in XP. What, however, about FPT? Do you have any ideas?