On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms | Algorithmica Skip to main content
Springer Nature Link
Log in

On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

For a graph G=(V,E) and a color set C, 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 in which all edges are assigned distinct colors. Chakraborty et al. defined the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. Chen et al. introduced the vertex-coloring version of the problem as a variant, and we introduce the total-coloring version in this paper. We settle the precise computational complexities of all the three problems with regards to graph diameters, and also characterize these with regards to certain graph classes: cacti, outer planer and series-parallel graphs. We then give FPT algorithms for the three problems on general graphs when parameterized by the number of colors in C; our FPT algorithms imply that all the three problems can be solved in polynomial time for any graph with n vertices if |C|=O(logn).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. We remark that the NP-completeness proof given by [8] does not imply Theorems 4 and 5.

References

  1. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42, 844–856 (1996)

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  3. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)

    Book  MATH  Google Scholar 

  4. Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness and algorithms for rainbow connection. J. Comb. Optim. 21, 330–347 (2011)

    Article  MathSciNet  Google Scholar 

  5. Chandran, L.S., Das, A., Rajendraprasad, D., Varma, N.M.: Rainbow connection number and connected dominating sets. Electron. Notes Discrete Math. 38, 239–244 (2011)

    Article  Google Scholar 

  6. Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008)

    MathSciNet  MATH  Google Scholar 

  7. Chartrand, C., Johns, G.L., McKeon, K.A., Zhang, P.: The rainbow connectivity of a graph. Networks 54, 75–81 (2009)

    Article  MathSciNet  Google Scholar 

  8. Chen, L., Li, X., Shi, Y.: The complexity of determining the rainbow vertex-connection of a graph. Theor. Comput. Sci. 412, 4531–4535 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  9. Caro, Y., Lev, A., Roditty, Y., Tuza, Z., Yuster, R.: On rainbow connectivity. Electron. J. Comb. 15, R57 (2008)

    MathSciNet  Google Scholar 

  10. Fellows, M.R., Guo, J., Kanj, I.: The parameterized complexity of some minimum label problems. J. Comput. Syst. Sci. 76, 727–740 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  13. Uchizawa, K., Aoki, T., Ito, T., Suzuki, A., Zhou, X.: On the rainbow connectivity of graphs: complexity and FPT algorithms. In: Proc. of COCOON 2011. LNCS, vol. 6842, pp. 86–97 (2011)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, Sendai, 980-8579, Japan

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki & Xiao Zhou

Authors
  1. Kei Uchizawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Takanori Aoki
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Takehiro Ito
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Akira Suzuki
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xiao Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kei Uchizawa.

Additional information

An extended abstract of this paper has been presented at the 17th Annual International Computing and Combinatorics Conference (COCOON 2011) [13].

This work is partially supported by Grant-in-Aid for Scientific Research.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Uchizawa, K., Aoki, T., Ito, T. et al. On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms. Algorithmica 67, 161–179 (2013). https://doi.org/10.1007/s00453-012-9689-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-012-9689-4

Keywords

Search

Navigation