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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.