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!

Improve this question
$\endgroup$
10
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 15:25

1 Answer 1

Reset to default
16
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2013 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, 2013 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, 2013 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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