17

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!

Tyson Williams
  • 4,258
  • 2
  • 23
  • 44
RIC_Eien
  • 439
  • 2
  • 4
  • 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 Apr 27 '13 at 23:53
  • 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 May 02 '13 at 04:10
  • 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 May 02 '13 at 06:33
  • 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 May 02 '13 at 15:10
  • @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 May 02 '13 at 15:25
  • @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 May 03 '13 at 03:01
  • @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 May 15 '13 at 19:41
  • 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 May 16 '13 at 17:31
  • @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 May 17 '13 at 16:20
  • @RIC_Eien: I don't have a reference for you, I just thought about it myself and discussed with Marek Chrobak. – Neal Young May 18 '13 at 17:18

1 Answers1

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.

The parameterized complexity aspects of this problem is addressed in this recent paper.

vb le
  • 4,828
  • 1
  • 37
  • 46
  • 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 Jun 17 '13 at 21:18
  • 5
    @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 Jun 21 '13 at 22:47
  • 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 has several detailed results. – Neeldhara Jun 29 '13 at 18:23