<p>This problem is NP-hard and APX-hard; see: Adamaszek and Popa, 
<em>Approximation and Hardness Results for the Maximum Edge $q$-coloring 
Problem</em>, <a href="http://link.springer.com/chapter/10.1007/978-3-642-17514-5_12">Lecture Notes in Computer Science 6507 (2010) 132-143</a>.</p>

<p>The parameterized complexity aspects of this problem is addressed in this recent <a href="http://arxiv.org/abs/1306.2931">paper</a>.</p>

CC BY-SA 3.0
2013-06-17T21:18:15.173Z
I have been thinking for while about this nice problem... Can you please describe the reduction? I don't have access to the paper. Thanks!
user13667
CC BY-SA 3.0
2013-06-21T22:47:01.837Z
@user13667 You can ask the authors for sending you a copy of their paper. I think they would be happy to do so.
vb le
CC BY-SA 3.0
2013-06-29T18:23:45.427Z
The related question of finding a coloring that maximizes the number of colors while minimizing the size of the largest color group is has also been studied. For example, this [Masters' Thesis](https://aaltodoc.aalto.fi/bitstream/handle/123456789/8981/master_Larjomaa_Tommi_2013.pdf?sequence=1) has several detailed results.
Neeldhara
CC BY-SA 3.0
2013-06-13T09:15:35.020Z
2013-06-28T12:21:07.240Z
2013-06-28T12:21:07.240Z
vb le
<p>Recently, I have encountered the following variant of edge coloring.</p>

<blockquote>
  <p>Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges incident to $v$ use at most two colors.</p>
</blockquote>

<p>My first guess is that the problem is NP-hard. Classical NP-hard proofs for graph coloring problems are mostly by reduction from 3SAT. But in my opinion, these proofs are not useful for this problem because edges incident to a vertex can be colored with the same color, so we cannot construct logic components in the graph.</p>

<p>Could this problem be NP-hard? If yes, what is a proof? If we cannot fine a proof, is there any method to determine the complexity of this problem?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2013-04-27T23:53:55.153Z
Perhaps Mixed or Colour-bounded Hypergraph Colouring might be a start?  For instance, http://dx.doi.org/10.1016/j.disc.2008.04.019
András Salamon
CC BY-SA 3.0
2013-05-02T04:10:55.693Z
It seems your problem is in P, in two steps: (1) your problem is equivalent to finding a maximum-size subset of the edges such that every vertex has degree at most two, and (2) the latter problem seems to be in P by, say, reduction to matching.  Regarding (1), note that any solution to your problem with k colors gives a degree-2 subgraph of size k (just retain one edge from each color), and conversely any degree-2 subgraph of size k gives a solution with k colors (just color each edge in the subgraph its own color, color the rest of the edges with any one of the colors).  What am I missing?
Neal Young
CC BY-SA 3.0
2013-05-02T06:33:04.000Z
I am sorry that there are several mistakes in your answer. At first, the problem "finding a maximum-size subset of the edges such that every vertex has degree at most two", is NP-hard, reduction to 3SAT(I do not really know how could it have reduction to matching). What's more, "any degree-2 subgraph of size k" does not give "a solution with k colors", for example, Complete Graph. Thank you all the same.
RIC_Eien
CC BY-SA 3.0
2013-05-02T15:10:32.943Z
Yes, you're right.  About (2), the step "color the rest of the edges with any one of the colors" can give some vertex edges of three colors.  Separately, Marek Chrobak suggested the following algorithm to me.  I think it gives a 3-approximation: (i) find a maximum matching M; (ii) color each edge in M its own unique color; (iii) color the remaining edges white.
Neal Young
CC BY-SA 3.0
2013-05-02T15:25:37.897Z
@RIC_Eien: At the risk of further embarrassment..  Are you sure "the problem 'finding a maximum-size subset of the edges such that every vertex has degree at most two', is NP-hard"?  Given G=(V,E), create bipartite G2=(U,W,E2), where for each vertex v in V there is v' in U and v'' in W, and E2={(u',w'') : (u,w) in E}.  Then the matchings in G2 correspond to the degree-2 sets of edges in G, and the correspondence preserves size?  (As each k-cycle C in G corresponds in G2 to either a 2k-cycle (if k odd) or two k-cycles (if k even).)  So max-matching in G2 solves it.  What am I missing this time?
Neal Young
CC BY-SA 3.0
2013-05-03T03:01:19.563Z
@NealYoung: I see, it's my fault(I did feel a little embarrassed). I considered "finding a maximum-size subset of the edges such that every vertex has degree at most two" as another problem... I'm so sorry for my carelessness. And about this problem, so, we could not prove that it's P, right? Back to the start.
RIC_Eien
CC BY-SA 3.0
2013-05-15T19:41:54.240Z
@NealYoung: I just found that there may be some fault in your proof on "the problem 'finding a maximum-size subset of the edges such that every vertex has degree at most two', is P", specifically in reduction to max-matching. If an edge was chosen without any other edges chosen incident to it, this edge would be counted twice in the bipartite. It means that sometimes max-matching of the bipartite would lead to a wrong answer.
RIC_Eien
CC BY-SA 3.0
2013-05-16T17:31:43.887Z
I see, so if G=(V,E) with V={a,b} and E={(a,b)} then G2 has a matching of size 2 but G does not have a subset of 2 edges (giving degree at most two to each vertex).  Yes, you're right -- that's a problem.
Neal Young
CC BY-SA 3.0
2013-05-17T16:20:52.627Z
@NealYoung: Right. I think the complexity of this problem would have been judged by others but I have not found any relative information. Did you think it out by yourself, or by some impression you had learned about it?
RIC_Eien
CC BY-SA 3.0
2013-05-18T17:18:48.270Z
@RIC_Eien: I don't have a reference for you, I just thought about it myself and discussed with Marek Chrobak.
Neal Young
<cc.complexity-theory><np-hardness><complexity-classes><graph-colouring>
What is the complexity of this edge coloring problem?
RIC_Eien
# What is the complexity of this edge coloring problem?

(Asked by: username_0 on 2013-04-27)

Recently, I have encountered the following variant of edge coloring.

> Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges incident to $v$ use at most two colors.

My first guess is that the problem is NP-hard. Classical NP-hard proofs for graph coloring problems are mostly by reduction from 3SAT. But in my opinion, these proofs are not useful for this problem because edges incident to a vertex can be colored with the same color, so we cannot construct logic components in the graph.

Could this problem be NP-hard? If yes, what is a proof? If we cannot fine a proof, is there any method to determine the complexity of this problem?

Thanks!

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, graph-colouring

> **Comments:**
> **username_1**: Perhaps Mixed or Colour-bounded Hypergraph Colouring might be a start?  For instance, http://dx.doi.org/10.1016/j.disc.2008.04.019  
> **username_2**: It seems your problem is in P, in two steps: (1) your problem is equivalent to finding a maximum-size subset of the edges such that every vertex has degree at most two, and (2) the latter problem seems to be in P by, say, reduction to matching.  Regarding (1), note that any solution to your problem with k colors gives a degree-2 subgraph of size k (just retain one edge from each color), and conversely any degree-2 subgraph of size k gives a solution with k colors (just color each edge in the subgraph its own color, color the rest of the edges with any one of the colors).  What am I missing?  
> **username_0**: I am sorry that there are several mistakes in your answer. At first, the problem "finding a maximum-size subset of the edges such that every vertex has degree at most two", is NP-hard, reduction to 3SAT(I do not really know how could it have reduction to matching). What's more, "any degree-2 subgraph of size k" does not give "a solution with k colors", for example, Complete Graph. Thank you all the same.  
> **username_2**: Yes, you're right.  About (2), the step "color the rest of the edges with any one of the colors" can give some vertex edges of three colors.  Separately, Marek Chrobak suggested the following algorithm to me.  I think it gives a 3-approximation: (i) find a maximum matching M; (ii) color each edge in M its own unique color; (iii) color the remaining edges white.  
> **username_2**: @username_0: At the risk of further embarrassment..  Are you sure "the problem 'finding a maximum-size subset of the edges such that every vertex has degree at most two', is NP-hard"?  Given G=(V,E), create bipartite G2=(U,W,E2), where for each vertex v in V there is v' in U and v'' in W, and E2={(u',w'') : (u,w) in E}.  Then the matchings in G2 correspond to the degree-2 sets of edges in G, and the correspondence preserves size?  (As each k-cycle C in G corresponds in G2 to either a 2k-cycle (if k odd) or two k-cycles (if k even).)  So max-matching in G2 solves it.  What am I missing this time?  
> **username_0**: @NealYoung: I see, it's my fault(I did feel a little embarrassed). I considered "finding a maximum-size subset of the edges such that every vertex has degree at most two" as another problem... I'm so sorry for my carelessness. And about this problem, so, we could not prove that it's P, right? Back to the start.  
> **username_0**: @NealYoung: I just found that there may be some fault in your proof on "the problem 'finding a maximum-size subset of the edges such that every vertex has degree at most two', is P", specifically in reduction to max-matching. If an edge was chosen without any other edges chosen incident to it, this edge would be counted twice in the bipartite. It means that sometimes max-matching of the bipartite would lead to a wrong answer.  
> **username_2**: I see, so if G=(V,E) with V={a,b} and E={(a,b)} then G2 has a matching of size 2 but G does not have a subset of 2 edges (giving degree at most two to each vertex).  Yes, you're right -- that's a problem.  
> **username_0**: @NealYoung: Right. I think the complexity of this problem would have been judged by others but I have not found any relative information. Did you think it out by yourself, or by some impression you had learned about it?  
> **username_2**: @username_0: I don't have a reference for you, I just thought about it myself and discussed with Marek Chrobak.  

---

## 1 answers

### Answer by username_3 on 2013-06-13. Score: 16

This problem is NP-hard and APX-hard; see: Adamaszek and Popa,
*Approximation and Hardness Results for the Maximum Edge $q$-coloring
Problem*, [Lecture Notes in Computer Science 6507 (2010) 132-143](http://link.springer.com/chapter/10.1007/978-3-642-17514-5_12).

The parameterized complexity aspects of this problem is addressed in this recent [paper](http://arxiv.org/abs/1306.2931).

> **Comments:**
> **username_4**: I have been thinking for while about this nice problem... Can you please describe the reduction? I don't have access to the paper. Thanks!  
> **username_3**: @username_4 You can ask the authors for sending you a copy of their paper. I think they would be happy to do so.  
> **username_5**: The related question of finding a coloring that maximizes the number of colors while minimizing the size of the largest color group is has also been studied. For example, this [Masters' Thesis](https://aaltodoc.aalto.fi/bitstream/handle/123456789/8981/master_Larjomaa_Tommi_2013.pdf?sequence=1) has several detailed results.  

---

