# Parameterized Complexity of Minimum Type Selection

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?

• What is your parameter, $k$ or $l$? (or $k+l$?). – R B Feb 20 '15 at 17:39
• As described, it is $k$. – Oliver Witt Feb 20 '15 at 20:05