Abstract
We consider the problem of deciding whether a k-colored graph can be completed to have a given property. We establish that, when k is not fixed, the completion problem for circular-arc graphs, even unit or proper circular-arc graphs, is NP-complete. When k is fixed, in the case of completion to circular-arc graphs and Helly circular-arc graphs, we fully classify the complexities of the problems. We also show that deciding whether a 3-colored graph can be completed to be strongly chordal can be done in O(n 2) time. As a corollary of our results, the sandwich problem for Helly circular-arc graphs is NP-complete.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alvarez, C., Diaz, J., Serna, M.: The hardness of intervalizing four colored caterpillars. Discrete Math. 235, 245–253 (2001)
Alvarez, C., Serna, M.: The proper interval colored graph problem for caterpillar trees. Electron. Notes in Discrete Math. 17, 23–28 (2004)
Bodlaender, H.L., de Fluiter, B.: On intervalizing k-colored graphs for DNA physical mapping. Discrete Appl. Math. 71, 55–77 (1996)
Bodlaender, H.L., Fellows, M.R., Warnow, T.J.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 273–283. Springer, Heidelberg (1992)
Bodlaender, H.L., Kloks, T.: A simple linear time algorithm for triangulating three-colored graphs. J. Algorithms 15, 160–172 (1993)
Fellows, M.R., Hallett, M.T., Warcham, H.T.: DNA physical mapping: three ways difficult. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 157–168. Springer, Heidelberg (1993)
de Figueiredo, C.M.H., Faria, L., Klein, S., Sritharan, R.: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs. Theoret. Comput. Sci. 381, 57–67 (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to NP-Completness. Freeman, New York (1979)
Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping. J. Comput. Biol. 2, 139–152 (1995)
Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. J. Algorithms 19, 449–473 (1995)
Idury, R., Schaffer, A.: Triangulating three-colored graphs in linear time and linear space. SIAM J. Discrete Math. 2, 289–293 (1993)
Kannan, S.K., Warnow, T.J.: Triangulating 3-colored graphs. SIAM J. Discrete Math. 5, 249–258 (1992)
Matousek, J., Thomas, R.: Algorithms finding tree-decompositions of graphs. J. Algorithms 12, 1–22 (1991)
McMorris, F.R., Warnow, T.J., Wimer, T.: Triangulaing vertex-colored graphs. SIAM J. Discrete Math. 7, 296–306 (1994)
Sritharan, R.: Chordal bipartite completion of colored graphs. Discrete Math. 308, 2581–2588 (2008)
Tucker, A.: An efficent test for circular arc graphs. SIAM J. Comput. 9, 1–24 (1980)
Warnow, T.J.: Combinatorial algorithms for constructing phylogenetic trees, Ph. D. Thesis, University of California, Berkeley (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cook, K., Eschen, E.M., Sritharan, R., Wang, X. (2013). Completing Colored Graphs to Meet a Target Property. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 2013. Lecture Notes in Computer Science, vol 8165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45043-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-45043-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45042-6
Online ISBN: 978-3-642-45043-3
eBook Packages: Computer ScienceComputer Science (R0)