Hardness and Algorithms for Rainbow Connection
| dc.creator | Chakraborty, Sourav | |
| dc.creator | Fischer, Eldar | |
| dc.creator | Matsliah, Arie | |
| dc.creator | Yuster, Raphael | |
| dc.date | 2008-09-15 | |
| dc.date.accessioned | 2026-07-07T10:02:50Z | |
| dc.date.available | 2026-07-07T10:02:50Z | |
| dc.description | 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 $ε>0$, a connected graph with minimum degree at least $εn$ has {\em bounded} rainbow connection, where the bound depends only on $ε$, 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. | |
| dc.identifier | https://arxiv.org/abs/0809.2493 | |
| dc.identifier | http://arxiv.org/abs/0809.2493 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/169113 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C85; 05C15 | |
| dc.title | Hardness and Algorithms for Rainbow Connection | |
| dc.type | text |