Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lam, T., Lanman, J., Emmett, M., Hendrickson, C., Marshall, A.G., Prevelige, P.: Mapping of protein:protein contact surfaces by hydrogen/deuterium exchange, followed by on-line high-performance liquid chromatography-electrospray ionization fourier-transform ion-cyclotron-resonance mass analysis. Journal of Chromatography A 982(1), 85–95 (2002)
Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing 5(4), 691–703 (1976)
Althaus, E., Canzar, S., Emmett, M.R., Karrenbauer, A., Marshall, A.G., Meyer-Baese, A., Zhang, H.: Computing of H/D-Exchange Speeds of Single Residues form Data of Peptic Fragments. In: Proceedings of the 23rd Annual ACM Symposium on Applied Computing 2008, pp. 1273–1277 (2008)
Althaus, E., Canzar, S., Elbassioni, K., Karrenbauer, A., Mestre, J.: Approximating the interval constrained coloring problem. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 210–221. Springer, Heidelberg (2008)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324–360 (2006)
Canzar, S.: Lagrangian Relaxation - Solving NP-hard problems in Computational Biology via Combinatorial Optimization. PhD thesis, Universität des Saarlandes (2008)
Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Deconstructing Intractability - A Case Study for Interval Constrained Coloring. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol. 5577, pp. 207–220. Springer, Heidelberg (2009)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)
Dinur, I.: The pcp theorem by gap amplification. J. ACM 54(3), 12 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Byrka, J., Karrenbauer, A., Sanità, L. (2010). The Interval Constrained 3-Coloring Problem. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)