TY - GEN
T1 - The interval constrained 3-coloring problem
AU - Byrka, Jaroslaw
AU - Karrenbauer, Andreas
AU - Sanità, Laura
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77953495962&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-12200-2_51
DO - 10.1007/978-3-642-12200-2_51
M3 - Conference contribution
AN - SCOPUS:77953495962
SN - 3642121993
SN - 9783642121999
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 591
EP - 602
BT - LATIN 2010
T2 - 9th Latin American Theoretical Informatics Symposium, LATIN 2010
Y2 - 19 April 2010 through 23 April 2010
ER -