#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!!!

Leave a Reply

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