The interval constrained 3-coloring problem

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-complete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. We also show that it is hard to satisfy almost all of the constraints for a feasible instance. This implies APX-hardness of maximizing the number of simultaneously satisfiable intervals.


Published in:
Lecture Notes in Computer Science, 6034, 591-602
Presented at:
9th Latin American Theoretical Informatics Symposium (LATIN), Oaxaca, Mexico, April 19-23, 2010
Year:
2010
Publisher:
Springer Verlag
ISSN:
0302-9743
Keywords:
Laboratories:




 Record created 2010-02-03, last modified 2018-01-28

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)