# #StackBounty: #optimization #computational-geometry #scheduling #intervals Finding a rainbow independent set in a circle

### Bounty: 50

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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.