  The anti-Ramsey numbers are a fundamental notion in graph theory, introduced
in 1978, by Erd\" os, Simonovits and S\' os. For given graphs $G$ and $H$ the
\emph{anti-Ramsey number} $\textrm{ar}(G,H)$ is defined to be the maximum
number $k$ such that there exists an assignment of $k$ colors to the edges of
$G$ in which every copy of $H$ in $G$ has at least two edges with the same
color.
  There are works on the computational complexity of the problem when $H$ is a
star. Along this line of research, we study the complexity of computing the
anti-Ramsey number $\textrm{ar}(G,P_k)$, where $P_k$ is a path of length $k$.
First, we observe that when $k = \Omega(n)$, the problem is hard; hence, the
challenging part is the computational complexity of the problem when $k$ is a
fixed constant.
  We provide a characterization of the problem for paths of constant length.
Our first main contribution is to prove that computing $\textrm{ar}(G,P_k)$ for
every integer $k>2$ is NP-hard. We obtain this by providing several structural
properties of such coloring in graphs. We investigate further and show that
approximating $\textrm{ar}(G,P_3)$ to a factor of $n^{-1/2 - \epsilon}$ is hard
already in $3$-partite graphs, unless P=NP. We also study the exact complexity
of the precolored version and show that there is no subexponential algorithm
for the problem unless ETH fails for any fixed constant $k$.
  Given the hardness of approximation and parametrization of the problem, it is
natural to study the problem on restricted graph families. We introduce the
notion of color connected coloring and employing this structural property. We
obtain a linear time algorithm to compute $\textrm{ar}(G,P_k)$, for every
integer $k$, when the host graph, $G$, is a tree.
