Top

Published in:

2018 | OriginalPaper | Chapter

Maximum Colorful Cycles in Vertex-Colored Graphs

Authors : Giuseppe F. Italiano, Yannis Manoussakis, Nguyen Kim Thang, Hong Phong Pham

Published in: Computer Science – Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we study the problem of finding a maximum colorful cycle a vertex-colored graph. Specifically, given a graph with colored vertices, the goal is to find a cycle containing the maximum number of colors. We aim to give a dichotomy overview on the complexity of the problem. We first show that the problem is NP-hard even for simple graphs such as split graphs, biconnected graphs, interval graphs. Then we provide polynomial-time algorithms for classes of vertex-colored threshold graphs and vertex-colored bipartite chain graphs, which are our main contributions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Periodicity in Data Streams with Wildcards

next chapter Grammar-Based Compression of Unranked Trees

Akbari, S., Liaghat, V., Nikzad, A.: Colorful paths in vertex coloring of graphs. Electron. J. Comb. 18(1), P17 (2011)MathSciNetMATH

Akiyama, T., Nishizeki, T., Saito, N.: Np-completeness of the hamiltonian cycle problem for bipartite graphs. J. Inf. Proc. 3(2), 73–76 (1979)MathSciNetMATH

Bertossi, A.A.: Finding Hamiltonian circuits in proper interval graphs. Inf. Proc. Lett. 17(2), 97–101 (1983)MathSciNetCrossRefMATH

Bruckner, S., Hüffner, F., Komusiewicz, C., Niedermeier, R.: Evaluation of ILP-based approaches for partitioning into colorful components. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 176–187. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38527-8_17CrossRef

Cohen, J., Manoussakis, Y., Pham, H., Tuza, Z.: Tropical matchings in vertex-colored graphs. In: Latin and American Algorithms, Graphs and Optimization Symposium (2017)MathSciNetCrossRefMATH

Cohen, J., Italiano, G.F., Manoussakis, Y., Nguyen, K.T., Pham, H.P.: Tropical paths in vertex-colored graphs. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017. LNCS, vol. 10628, pp. 291–305. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71147-8_20CrossRef

Corel, E., Pitschi, F., Morgenstern, B.: A min-cut algorithm for the consistency problem in multiple sequence alignment. Bioinformatics 26(8), 1015–1021 (2010)CrossRef

Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799–811 (2011)MathSciNetCrossRefMATH

Foucaud, F., Harutyunyan, A., Hell, P., Legay, S., Manoussakis, Y., Naserasr, R.: Tropical homomorphisms in vertex-coloured graphs. Discrete App. Math. (to appear)

10.

Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings 6th Symposium on Theory of Computing, pp. 47–63 (1974)

11.

Ibarra, L.: A simple algorithm to find Hamiltonian cycles in proper interval graphs. Inf. Proc. Lett. 109(18), 1105–1108 (2009b)MathSciNetCrossRefMATH

12.

Li, H.: A generalization of the Gallai-Roy theorem. Graphs Comb. 17(4), 681–685 (2001)MathSciNetCrossRefMATH

13.

Lin, C.: Simple proofs of results on paths representing all colors in proper vertex-colorings. Graphs Comb. 23(2), 201–203 (2007)MathSciNetCrossRefMATH

14.

Mahadev, N.V.R., Peled, U.N.: Longest cycles in threshold graphs. Discrete Math. 135(1–3), 169–176 (1994)MathSciNetCrossRefMATH

15.

Marx, D.: Graph colouring problems and their applications in scheduling. Periodica Polytech. Electr. Eng. 48(1–2), 11–16 (2004)

16.

Micali, S., Vazirani, V.V.: An \({O}(\sqrt{|V|} |{E}|)\) algorithm for finding maximum matching in general graphs. In: Proceedings 21st Symposium on Foundations of Computer Science, pp. 17–27 (1980)

17.

Uehara, R., Valiente, G.: Linear structure of bipartite permutation graphs and the longest path problem. Inf. Proc. Lett. 103(2), 71–77 (2007)MathSciNetCrossRefMATH

Title: Maximum Colorful Cycles in Vertex-Colored Graphs
Authors: Giuseppe F. Italiano
Yannis Manoussakis
Nguyen Kim Thang
Hong Phong Pham
Publisher: Springer International Publishing
Book: Computer Science – Theory and Applications
Print ISBN: 978-3-319-90529-7

Electronic ISBN: 978-3-319-90530-3

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-90530-3_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner