1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What is your question? Please ask only one question per post. $\endgroup$
    – D.W.
    Commented May 27, 2022 at 21:08

1 Answer 1

5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.