Hardness and Algorithms for Rainbow Connectivity

Authors Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster



PDF
Thumbnail PDF

File

LIPIcs.STACS.2009.1811.pdf
  • Filesize: 142 kB
  • 12 pages

Document Identifiers

Author Details

Sourav Chakraborty
Eldar Fischer
Arie Matsliah
Raphael Yuster

Cite AsGet BibTex

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Raphael Yuster. Hardness and Algorithms for Rainbow Connectivity. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 243-254, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.STACS.2009.1811

Abstract

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 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 NP-Hard. 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 bounded rainbow connectivity, where the bound depends only on $\epsilon$, and the corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail