A few days ago I had a test and could not pass it. This is a question I did not understand in the test.

We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G = (V, E) and natural number k and ask "Is there a coloration in arcs of G which uses at most k colors?". Remember, while painting vertices to two neighboring vertices must not have the same color, painting arcs to two neighboring arcs (i.e., having a common vertex) must not be The same color. That is, the language is:

Edge-Coloring = {<G,k>|G can be arcuated by coloring using ≤ k colors}

Determine which of the following statements is correct:

  1. The language is in P. An algorithm can be constructed running at time O (| V | * | E |), by reduction to the vertex-Coloring problem and then verifying that each color is ≤ k.
  2. The language is in NP (and it is also possible that it is NP-complete, but this is not due to the question data)
  3. The language is NP-complete, which is why vertex-Coloring is NP-complete and also $Edge-coloring \leq _pvertex-coloring $ can be performed by converting each arc to a vertex.
  4. The language is NP-complete but not in NP
  5. None of the above claims are true.

I think 3 is true, because in my opinion a reduction is made from the vertex-coloring problem which is NPC, and also the edge-coloring problem should be in NPC.

But I can not rule out 4, 2 and 5.


2 Answers 2

  1. We don't know whether this is true.

  2. This is true, a certificate is an edge coloring with at most $k$ colors.

  3. This is true. Edge coloring is a well-known NP-hard problem (see here for a reduction from 3-SAT) and hence there is Karp reduction from every problem in NP to it. In particular there must also be a reduction from vertex coloring (which is NP-hard) to edge coloring. The reduction from edge coloring to vertex coloring creates a vertex $v_e$ for every edge $e$ in $G$ and an edge $(v_e, v_f)$ for every pair of distinct edges $e$ and $f$ in $G$ that share an endpoint.

  4. This statement is clearly false since all NP-complete languages are in NP by definition.

  5. This is false since, e.g., 2 is true.

  • $\begingroup$ Thanks for the help, the test has only one correct answer, and the solution you offered me contains 2 correct answers, also 2 and 3 correct actually? $\endgroup$
    – hch
    Jul 20, 2021 at 12:23
  • 1
    $\begingroup$ Edge coloring is NP-complete (and hence it is in NP). It can shown to be NP-complete by observing that it is in NP and that vertex coloring is NP-complete (using the fact that vertex coloring $\le_p$ edge coloring as I argue in my answer). Moreover, it is also true that edge coloring $\le_p$ vertex coloring. Probably answer number 3 should have been worded as follows "The language is NP-Complete because there is a Karp reduction from vertex coloring to edge coloring". This claim would be false since you need the reduction to be in the opposite direction. $\endgroup$
    – Steven
    Jul 20, 2021 at 12:48
  • For (3), you are correct, i.e., the problem is NP-complete. As a side note, you might also like to know that you can solve edge coloring by using vertex coloring algorithms by taking the line graph. Note that this in itself does not prove NP-completeness.

  • For (2), you need to show that if you given a certificate, then you can verify it in polynomial time. In this case, the certificate is the coloring, i.e., a color per edge. Given that certificate, you can easily check in polynomial time whether the given coloring is a proper edge-coloring. I encourage you to check the details.

  • For (4), you should check the definition of NP-completeness. If a problem is NP-complete, then by definition it is also in NP.

  • Question (5) is now trivial.


Your Answer

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

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