×

Hardness and algorithms for rainbow connection. (English) Zbl 1319.05049

Summary: An edge-colored graph \(G\) is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph \(G\), denoted \(\operatorname{rc}(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow connected. In the first result of this paper we prove that computing \(\operatorname{rc}(G)\) is NP-Hard solving an open problem from Y. Caro et al. [Electron. J. Comb. 15, No. 1, Research Paper R57, 13 p. (2008; Zbl 1181.05037)]. In fact, we prove that it is already NP-Complete to decide if \(\operatorname{rc}(G)=2\), and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every \(\epsilon>0\), a connected graph with minimum degree at least \(\epsilon n\) has bounded rainbow connection, where the bound depends only on \(\epsilon\), and a corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.

MSC:

05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1181.05037
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon N, Spencer JH (2000) The probabilistic method, 2nd edn. Wiley, New York
[2] Alon N, Duke RA, Lefmann H, Rödl V, Yuster R (1994) The algorithmic aspects of the Regularity Lemma. J Algorithms 16:80–109 · Zbl 0794.05119 · doi:10.1006/jagm.1994.1005
[3] Blum A, Karger D (1997) An $\(\backslash\)tilde{O}(n\^{3/14})$ -coloring algorithm for 3-colorable graphs. Inf Process Lett 61(1):49–53 · Zbl 1337.05096 · doi:10.1016/S0020-0190(96)00190-1
[4] Caro Y, Lev A, Roditty Y, Tuza Z, Yuster R (2008) On rainbow connection, Electron J Comb 15, Paper R57 · Zbl 1181.05037
[5] Chartrand G, Johns GL, McKeon KA, Zhang P (2008) Rainbow connection in graphs. Math Bohem 133(1):85–98 · Zbl 1199.05106
[6] Fischer E, Matsliah A, Shapira A (2007) Approximate hypergraph partitioning and applications. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS), pp 579–589 · Zbl 1271.68113
[7] Komlós J, Simonovits M (1996) Szemerédi’s Regularity Lemma and its applications in graph theory. In: Miklós, D, Sós, VT, Szönyi, T (eds) Combinatorics, Paul Erdös is Eighty. Bolyai society mathematical studies, vol 2. Budapest, pp 295–352
[8] Szemerédi E (1978) Regular partitions of graphs. In: Proc. colloque inter. CNRS 260. CNRS, Paris, pp 399–401. · Zbl 0413.05055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.