<p>Consider the following problem that I call »Minimum Type Selection«:</p>

<ul>
<li>Input: $k$ sets of bit vectors, each of length $n$ and a number $l$.</li>
<li>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.</li>
</ul>

<p>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?</p>

CC BY-SA 3.0
2015-02-20T17:39:30.993Z
What is your parameter, $k$ or $l$? (or $k+l$?).
R B
CC BY-SA 3.0
2015-02-20T20:05:50.080Z
As described, it is $k$.
Oliver Witt
<matrices><parameterized-complexity>
Parameterized Complexity of Minimum Type Selection
Oliver Witt
# Parameterized Complexity of Minimum Type Selection

(Asked by: username_0 on 2015-02-20)

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?

**Tags:** matrices, parameterized-complexity
> **Comments:**
> **username_1**: What is your parameter, $k$ or $l$? (or $k+l$?).  
> **username_0**: As described, it is $k$.  

---

## 0 answers

