# Strong conflict-free coloring for intervals Academic Article

•
• Overview
•
• Research
•
•
• View All
•

### abstract

• We consider the $$k$$-strong conflict-free ($$k$$-SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval $$I$$ of the family there are at least $$k$$ colors each appearing exactly once in $$I$$. We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when $$k=1$$ and $$5-\frac{2}{k}$$ when $$k\ge 2$$. In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any $$k \ge 1$$. We also provide, in case $$k=O({{\mathrm{polylog}}}(n))$$, a quasipolynomial time algorithm to decide the existence of a $$k$$-SCF coloring that uses at most $$q$$ colors.

### publication date

• January 1, 2014