Complexity of computing the anti-Ramsey numbers.

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 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. Precolored version of the problem is defined in a similar way except that the input graph is given with some fixed colors on some of the edges. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. In this paper 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 the hardness of the problem when $k$ is not fixed and we study the exact complexity of precolored version and show that there is no subexponential algorithm for the problem unless ETH fails already for $k=3$. We show that computing the $\textrm{ar}(G,P_3)$ is hard to approximate to a factor of $n^{- 1/2 - \epsilon}$ even in $3$-partite graphs, unless $NP{}= {}ZPP$. On the positive side we provide polynomial time algorithm for trees and we show approximability of the problem on special classes of graphs.