Approximation and hardness results for the maximum edge q-coloring problem

Anna Adamaszek, Alexandru Popa

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalJournal of Discrete Algorithms
Volume38-41
DOIs
Publication statusPublished - May 1 2016

Fingerprint

Coloring
Hardness
Colouring
Approximation
Graph in graph theory
Edge Coloring
Approximation algorithms
Approximation Algorithms
Color
Perfect Matching
NP-complete problem
Computational complexity
Game
Vertex of a graph

Keywords

  • Approximation algorithms
  • Graph coloring
  • Hardness of approximation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Cite this

Approximation and hardness results for the maximum edge q-coloring problem. / Adamaszek, Anna; Popa, Alexandru.

In: Journal of Discrete Algorithms, Vol. 38-41, 01.05.2016, p. 1-8.

Research output: Contribution to journalArticle

Adamaszek, Anna ; Popa, Alexandru. / Approximation and hardness results for the maximum edge q-coloring problem. In: Journal of Discrete Algorithms. 2016 ; Vol. 38-41. pp. 1-8.
@article{f664ad31471441afaf6e786c6dd4ed95,
title = "Approximation and hardness results for the maximum edge q-coloring problem",
abstract = "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.",
keywords = "Approximation algorithms, Graph coloring, Hardness of approximation",
author = "Anna Adamaszek and Alexandru Popa",
year = "2016",
month = "5",
day = "1",
doi = "10.1016/j.jda.2016.09.003",
language = "English",
volume = "38-41",
pages = "1--8",
journal = "Journal of Discrete Algorithms",
issn = "1570-8667",
publisher = "Elsevier",

}

TY - JOUR

T1 - Approximation and hardness results for the maximum edge q-coloring problem

AU - Adamaszek, Anna

AU - Popa, Alexandru

PY - 2016/5/1

Y1 - 2016/5/1

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

UR - http://www.scopus.com/inward/citedby.url?scp=84991813327&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2016.09.003

DO - 10.1016/j.jda.2016.09.003

M3 - Article

VL - 38-41

SP - 1

EP - 8

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

ER -