Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Hardness and Algorithms for Rainbow Connection   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.

34
The categories of this paper are: chem-ph
15
The categories of this paper are: nucl-ex
6
The categories of this paper are: astro-ph
16
The categories of this paper are: stat
4
The categories of this paper are: cond-mat
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
1
The categories of this paper are: cs
11
The categories of this paper are: hep-lat
30
The categories of this paper are: q-alg
17
The categories of this paper are: q-fin
36
The categories of this paper are: cmp-lg
8
The categories of this paper are: hep-ex
14
The categories of this paper are: math-ph
25
The categories of this paper are: patt-sol
13
The categories of this paper are: quant-ph