Reduction from vertex-coloring problem to edge-coloring problem

Question

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.

Answer 1

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.

Answer 2

• 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.