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.
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
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)