7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Sep 2 at 15:08
  • 3
    $\begingroup$ @InuyashaYagami It is NP-complete. $\endgroup$
    – xskxzr
    Sep 3 at 2:11
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 5 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.