Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Suppose we are given $n$ points on the real line, where each point is colored with a color from set $C=\{c_1,c_2,\ldots,c_k\}$ that contains $k$ distinct colors. We try to cover the $k$ distinct colors with as few unit length intervals as possible.
I think this problem is NP-hard and we can reduce from set cover problem. But I get stuck.
Also when $k=3$, is there a polynomial solution. I read this link but I can't understand his idea?
If $k$ is part of the input then the problem is NP-hard and you can indeed reduce from the set-cover problem. Let $x_{1}, \dots, x_k$ be the items and $S_1, \dots, S_m$ be the sets. Create a color for each item. Then, for each set $S_i$, create $|S_i|$ points on the real line at coordinates $2i + \frac{1}{|S_i|}, 2i + \frac{2}{|S_i|}, \dots, 2i + 1$. Color the $j$-th of such points with the color of the $j$-th item in $S_i$. Notice that: (i) one interval cannot cover two points from two sets, and (ii) all points from the same set can be covered with a single interval.
If $k$ is not part of the input then the problem is not NP-hard, unless P=NP. Indeed a trivial algorithm guesses one covered point for each color (there are only $O(n^k)$ guesses) and then covers the guessed points with the minimum number of intervals (this can be done via an easy greedy algorithm).
