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

Anna Adamaszek, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

Abstract

We consider the problem of coloring edges of a graph subject to the following constraint: for every vertex v, all the edges incident to v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors. 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. We prove that for any integer q ≥ 2 the problem is NP-Hard and APX-Hard. We also present a 5/3-approximation algorithm for q = 2 for graphs with a perfect matching.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages132-143
Number of pages12
Volume6507 LNCS
EditionPART 2
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of
Duration: Dec 15 2010Dec 17 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume6507 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
CountryKorea, Republic of
CityJeju Island
Period12/15/1012/17/10

Fingerprint

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Adamaszek, A., & Popa, A. (2010). Approximation and hardness results for the maximum edge q-coloring problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (PART 2 ed., Vol. 6507 LNCS, pp. 132-143). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17514-5_12

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6507 LNCS PART 2. ed. 2010. p. 132-143 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Adamaszek, A & Popa, A 2010, Approximation and hardness results for the maximum edge q-coloring problem. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). PART 2 edn, vol. 6507 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6507 LNCS, pp. 132-143, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 12/15/10. https://doi.org/10.1007/978-3-642-17514-5_12
Adamaszek A, Popa A. Approximation and hardness results for the maximum edge q-coloring problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). PART 2 ed. Vol. 6507 LNCS. 2010. p. 132-143. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). https://doi.org/10.1007/978-3-642-17514-5_12
Adamaszek, Anna ; Popa, Alexandru. / Approximation and hardness results for the maximum edge q-coloring problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6507 LNCS PART 2. ed. 2010. pp. 132-143 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).
@inproceedings{afe5f98771b04c09b00896d9b001cc61,
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 constraint: for every vertex v, all the edges incident to v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors. 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. We prove that for any integer q ≥ 2 the problem is NP-Hard and APX-Hard. We also present a 5/3-approximation algorithm for q = 2 for graphs with a perfect matching.",
author = "Anna Adamaszek and Alexandru Popa",
year = "2010",
doi = "10.1007/978-3-642-17514-5_12",
language = "English",
isbn = "3642175163",
volume = "6507 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
number = "PART 2",
pages = "132--143",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
edition = "PART 2",

}

TY - GEN

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

AU - Adamaszek, Anna

AU - Popa, Alexandru

PY - 2010

Y1 - 2010

N2 - We consider the problem of coloring edges of a graph subject to the following constraint: for every vertex v, all the edges incident to v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors. 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. We prove that for any integer q ≥ 2 the problem is NP-Hard and APX-Hard. We also present a 5/3-approximation algorithm for q = 2 for graphs with a perfect matching.

AB - We consider the problem of coloring edges of a graph subject to the following constraint: for every vertex v, all the edges incident to v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors. 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. We prove that for any integer q ≥ 2 the problem is NP-Hard and APX-Hard. We also present a 5/3-approximation algorithm for q = 2 for graphs with a perfect matching.

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

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

U2 - 10.1007/978-3-642-17514-5_12

DO - 10.1007/978-3-642-17514-5_12

M3 - Conference contribution

SN - 3642175163

SN - 9783642175169

VL - 6507 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 132

EP - 143

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -