Hardness and Algorithms for Rainbow Connection

Details Hardness and Algorithms for Rainbow Connection Hardness and Algorithms for Rainbow Connection

2008-09-15

arxiv.org/abs/0809.2493v1

Mathematics

Combinatorics

Scientific paper

An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connection} of a connected graph $G$, denoted $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 $rc(G)$ is NP-Hard solving an open problem from \cite{Ca-Yu}. In fact, we prove that it is already NP-Complete to decide if $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 {\em 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.

Affiliated with

Also associated with

No associations

Rating

Hardness and Algorithms for Rainbow Connection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hardness and Algorithms for Rainbow Connection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardness and Algorithms for Rainbow Connection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-635083