  A vertex-colored graph is {\it rainbow vertex-connected} if any two vertices
are connected by a path whose internal vertices have distinct colors, which was
introduced by Krivelevich and Yuster. The {\it rainbow vertex-connection} of a
connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that
are needed in order to make $G$ rainbow vertex-connected. In this paper, we
study the computational complexity of vertex-rainbow connection of graphs and
prove that computing $rvc(G)$ is NP-Hard. Moreover, we show that it is already
NP-Complete to decide whether $rvc(G)=2$. We also prove that the following
problem is NP-Complete: given a vertex-colored graph $G$, check whether the
given coloring makes $G$ rainbow vertex-connected.
