17
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Perhaps Mixed or Colour-bounded Hypergraph Colouring might be a start? For instance, dx.doi.org/10.1016/j.disc.2008.04.019 $\endgroup$ – András Salamon Apr 27 '13 at 23:53
  • $\begingroup$ 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? $\endgroup$ – Neal Young May 2 '13 at 4:10
  • $\begingroup$ 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. $\endgroup$ – RIC_Eien May 2 '13 at 6:33
  • $\begingroup$ 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. $\endgroup$ – Neal Young May 2 '13 at 15:10
  • $\begingroup$ @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? $\endgroup$ – Neal Young May 2 '13 at 15:25
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – user13667 Jun 17 '13 at 21:18
  • 5
    $\begingroup$ @user13667 You can ask the authors for sending you a copy of their paper. I think they would be happy to do so. $\endgroup$ – vb le Jun 21 '13 at 22:47
  • 5
    $\begingroup$ 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. $\endgroup$ – Neeldhara Jun 29 '13 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.