TY - GEN
T1 - Complexity of computing the anti-ramsey numbers for paths
AU - Amiri, Saeed Akhoondian
AU - Popa, Alexandru
AU - Roghani, Mohammad
AU - Shahkarami, Golnoosh
AU - Soltani, Reza
AU - Vahidi, Hossein
N1 - Publisher Copyright:
© Nathalie Bertrand; licensed under Creative Commons License CC-BY 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/8/1
Y1 - 2020/8/1
N2 - The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdös, Simonovits and Sós. For given graphs G and H the anti-Ramsey number 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. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. 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 is close to 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. Along this line, we first 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.
AB - The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdös, Simonovits and Sós. For given graphs G and H the anti-Ramsey number 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. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. 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 is close to 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. Along this line, we first 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.
KW - Algorithm
KW - Anti-Ramsey
KW - Approximation
KW - Coloring
KW - ETH
KW - NP-hard
UR - http://www.scopus.com/inward/record.url?scp=85090505260&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090505260&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2020.6
DO - 10.4230/LIPIcs.MFCS.2020.6
M3 - Conference contribution
AN - SCOPUS:85090505260
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
A2 - Esparza, Javier
A2 - Kral�, Daniel
A2 - Kral�, Daniel
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
Y2 - 25 August 2020 through 26 August 2020
ER -