TY - JOUR
T1 - Approximation and hardness results for the maximum edge q-coloring problem
AU - Adamaszek, Anna Maria
AU - Popa, Alexandru
PY - 2016
Y1 - 2016
N2 - We consider the problem of coloring edges of a graph subject to the following constraints: for every vertex v, all the edges incident with v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraints and using the maximum number of colors. Notice that the notion of coloring is different than in the classical edge coloring problem, as neighboring edges can have the same color. This problem has been studied in the past from the combinatorial and algorithmic point of view. The optimal coloring is known for some special classes of graphs. There is also an approximation algorithm for general graphs, which in the case q=2 gives a 2-approximation. However, the complexity of finding the optimal coloring was not known. In this paper, we prove that the problem is NP-Hard for any q≥2. Moreover, we prove that it cannot be approximated within a factor of 1+1/q−ϵ for any ϵ>0 and any q≥2 assuming the unique games conjecture (UGC), or 1+−ϵ for any ϵ>0 and any q≥3 (≈1.19 for q=2) assuming P≠NP. These results hold even when the considered graphs are bipartite. On the algorithmic side, we restrict to the case q=2, since this is the most important in practice and we show a 5/3-approximation algorithm for graphs which have a perfect matching.
AB - We consider the problem of coloring edges of a graph subject to the following constraints: for every vertex v, all the edges incident with v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraints and using the maximum number of colors. Notice that the notion of coloring is different than in the classical edge coloring problem, as neighboring edges can have the same color. This problem has been studied in the past from the combinatorial and algorithmic point of view. The optimal coloring is known for some special classes of graphs. There is also an approximation algorithm for general graphs, which in the case q=2 gives a 2-approximation. However, the complexity of finding the optimal coloring was not known. In this paper, we prove that the problem is NP-Hard for any q≥2. Moreover, we prove that it cannot be approximated within a factor of 1+1/q−ϵ for any ϵ>0 and any q≥2 assuming the unique games conjecture (UGC), or 1+−ϵ for any ϵ>0 and any q≥3 (≈1.19 for q=2) assuming P≠NP. These results hold even when the considered graphs are bipartite. On the algorithmic side, we restrict to the case q=2, since this is the most important in practice and we show a 5/3-approximation algorithm for graphs which have a perfect matching.
KW - Approximation algorithms
KW - Graph coloring
KW - Hardness of approximation
UR - http://www.scopus.com/inward/record.url?scp=84991813327&partnerID=8YFLogxK
U2 - 10.1016/j.jda.2016.09.003
DO - 10.1016/j.jda.2016.09.003
M3 - Journal article
AN - SCOPUS:84991813327
SN - 0196-6774
VL - 38-41
SP - 1
EP - 8
JO - Journal of Algorithms
JF - Journal of Algorithms
ER -