Abstract
Let C = {c 1, c 2, …, c k } be a set of k colors, and let ℓ = (ℓ1, ℓ2, …, ℓ k ) be a k-tuple of nonnegative integers ℓ1, ℓ2, …, ℓ k . For a graph G = (V,E), let f: E → C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is ℓ-rainbow connected if every two vertices of G have a path P such that the number of edges in P that are colored with c j is at most ℓ j for each index j ∈ {1,2,…, k}. Given a k-tuple ℓ and an edge-colored graph, we study the problem of determining whether the edge-colored graph is ℓ-rainbow connected. In this paper, we characterize the computational complexity of the problem with regards to certain graph classes: the problem is NP-complete even for cacti, while is solvable in polynomial time for trees. We then give an FPT algorithm for general graphs when parameterized by both k and ℓ max = max { ℓ j |1 ≤ j ≤ k }.
This work is partially supported by JSPS KAKENHI Grant Numbers 22700001, 23500001 and 23700003.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42, 844–856 (1996)
Ananth, P., Mande, M., Sarpatwar, K.: Rainbow connectivity: hardness and tractability. In: Proc. of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, pp. 241–251 (2011)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)
Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness and algorithms for rainbow connection. J. Combinatorial Optimization 21, 330–347 (2011)
Chandran, L.S., Das, A., Rajendraprasad, D., Varma, N.M.: Rainbow connection number and connected dominating sets. J. Graph Theory 71, 206–218 (2012)
Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Mathematica Bohemica 133, 85–98 (2008)
Chartrand, C., Johns, G.L., McKeon, K.A., Zhang, P.: The rainbow connectivity of a graph. Networks 54, 75–81 (2009)
Caro, Y., Lev, A., Roditty, Y., Tuza, Z., Yuster, R.: On rainbow connectivity. The Electronic J. Combinatorics 15, R57 (2008)
Fellows, M.R., Guo, J., Kanj, I.: The parameterized complexity of some minimum label problems. J. Computer and System Sciences 76, 727–740 (2010)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Krivelevich, M., Yuster, R.: The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J. Graph Theory 63, 185–191 (2010)
Uchizawa, K., Aoki, T., Ito, T., Suzuki, A., Zhou, X.: On the rainbow connectivity of graphs: complexity and FPT algorithms. To appear in Algorithmica, doi:10.1007/s00453-012-9689-4
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
Uchizawa, K., Aoki, T., Ito, T., Zhou, X. (2013). Generalized Rainbow Connectivity of Graphs. In: Ghosh, S.K., Tokuyama, T. (eds) WALCOM: Algorithms and Computation. WALCOM 2013. Lecture Notes in Computer Science, vol 7748. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36065-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-36065-7_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36064-0
Online ISBN: 978-3-642-36065-7
eBook Packages: Computer ScienceComputer Science (R0)