Chakraborty, Sourav ;
Fischer, Eldar ;
Matsliah, Arie ;
Yuster, Raphael
Hardness and Algorithms for Rainbow Connectivity
Abstract
An edgecolored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connectivity} 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 addition to being a natural combinatorial problem, the rainbow connectivity problem is motivated by applications in cellular networks. In this paper we give the first proof that computing $rc(G)$ is NPHard. In fact, we prove that it is already NPComplete to decide if $rc(G)=2$, and also that it is NPComplete to decide whether a given edgecolored (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 connectivity, where the bound depends only on $\epsilon$, and the corresponding coloring can be constructed in polynomial time. Additional nontrivial upper bounds, as well as open problems and conjectures are also presented.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs:2009:1811,
author = {Sourav Chakraborty and Eldar Fischer and Arie Matsliah and Raphael Yuster},
title = {{Hardness and Algorithms for Rainbow Connectivity}},
booktitle = {26th International Symposium on Theoretical Aspects of Computer Science},
pages = {243254},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897095},
ISSN = {18688969},
year = {2009},
volume = {3},
editor = {Susanne Albers and JeanYves Marion},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1811},
URN = {urn:nbn:de:0030drops18115},
doi = {10.4230/LIPIcs.STACS.2009.1811},
annote = {Keywords: }
}
2009
Seminar: 

26th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2009 
Date of publication: 

2009 