Hardness and Algorithms for Rainbow Connectivity
| dc.creator | Chakraborty, Sourav | |
| dc.creator | Fischer, Eldar | |
| dc.creator | Matsliah, Arie | |
| dc.creator | Yuster, Raphael | |
| dc.date | 2009-02-07 | |
| dc.date | 2009-02-17 | |
| dc.date.accessioned | 2026-07-07T12:42:03Z | |
| dc.date.available | 2026-07-07T12:42:03Z | |
| dc.description | An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The 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 $ε$ > 0, a connected graph with minimum degree at least $εn$ has bounded rainbow connectivity, where the bound depends only on $ε$, and the corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also pre sented. | |
| dc.identifier | https://arxiv.org/abs/0902.1255 | |
| dc.identifier | http://arxiv.org/abs/0902.1255 | |
| dc.identifier | 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 243-254 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/219946 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.title | Hardness and Algorithms for Rainbow Connectivity | |
| dc.type | text |