# Finding a rainbow independent set in a circle

Inside the interval $$[0,1]$$, there are $$n^2$$ intervals of $$n$$ different colors: $$n$$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $$n$$ pairwise-disjoint intervals, one of each color.

A rainbow independent set always exists and can be found easily: take an interval whose rightmost endpoint is leftmost (nearest to the $$0$$). Remove all intervals of the same color and all overlapping intervals of other colors. Note that at most one interval of any other color is removed, so now we have $$n-1$$ colors with $$n-1$$ intervals of each color, and can proceed recursively.

But now, suppose that the $$n^2$$ intervals are located inside a circle (that is, an interval with both endpoints identified). Here, a rainbow independent set might not exist even for $$n=2$$, for example, if the red intervals are $$(0,0.5)$$ and $$(0.5,1)$$ and the blue intervals are $$(0.25,0.75)$$ and $$(0.75,0.25)$$.

Is there a polynomial-time algorithm to decide whether a rainbow independent set exists?

NOTE: finding a rainbow-independent-set in a general graph is NP-hard, but this is a special case.

• Cosider the standard interval case $[0,1]$. Suppose there are some colors that have less than $n$ intervals. Now, a rainbow independent set might not exist. Is there any polynomial-time algorithm to decide the existence of a rainbow independent set in this case? Sep 2 at 15:08
• @InuyashaYagami It is NP-complete. Sep 3 at 2:11
• @xskxzr: Right, because the hardness proof given at your link makes no use of overlapping intervals within a group ( = of the same colour). But I'd like to point out that the GISDPk problem described there doesn't actually mandate that intervals within a group be non-overlapping, so that problem is a slight generalisation of Inuyasha's problem. Sep 5 at 10:44