Complexity of Computing the Anti-Ramsey Numbers for Paths

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 ar(G, Pk), where Pk is a path of length k. First, we observe that when k=Ω(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 ar(G, Pk) 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 ar(G, P3) to a factor of n−1/2−ϵ 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 ar(G, Pk), for every integer k, when the host graph, G, is a tree.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.