I study complexity and computation independently. I have a problem that I can not solve.
That's the problem:
Edge-Coloring problem, 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?". 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} Let's look at reduction, Edge-Coloring $\leq _p$ Vertex-Coloring According to the graph G = (V, E), built new vertices Group: $\widetilde{V}$ = {$x_e | e \in E$} We will define a new edge between two vertices, $x_{e_1}$ and $x_{e_2}$, if there is a common vertex between edges $e_1$ and $e_2$. $\widetilde{E}$ = {$(x_{e_1},x_{e_2}) | e_1 \cap e_2 \neq \phi $} Finally we will define: $\widetilde{G}$ = ($\widetilde{V}$ , $\widetilde{E}$)
The question has 3 parts, but they are related to each other, so I can not ask each question separately.
Section A
If the G edges can be painted in k colors, in how many colors the vertices can be painted in $\widetilde{G}$
- k
- 3k
- k^2
- |V|+1
- none of the answers is correct.
I think the correct answer is k, in graph G we have to color the edges, every edge in G becomes a vertex in
$\widetilde{G}$, and every vertex in G becomes an edge in
$\widetilde{G}$, which means there is symmetry. If in G the edges need to be painted in K colors then in
$\widetilde{G}$ the vertices need to be painted in K colors
Section B
Is this a polynomial reduction?
- yes.
- No, the amount of edges may be quadratic as a function of the amount of vertices.
- No, the amount of edges may be exponential as a function of the amount of vertices.
- You can not tell, depending on the size of the graph
- none of the answers is correct.
I think the correct answer is Yes , Each adge in G becomes a vertex in
$\widetilde{G}$ , a polynomial runtime as the size of the | E |. After this each edge in E can be connected to 2 vertices, and each vertex can be connected to all the other edges. For each edge we will check if it is connected to the other edges, running time of | E |^2.
Section C Is the reduction correct and well defined?
- Yes, reduction correct and well defined
- Although the reduction is correct, but it does not deal with cases where the original graph G was empty (without edges)
- Although the reduction is well defined for all graphs, it is incorrect when the number of edges is evaluated as a function of the number of vertices.
- No
- none of the answers is correct.
I feel like the answer is 1., but I have no explanation for it, here I actually think I'm stuck. How can you check that reduction correct and well defined?
I think this is a very easy question, but I could not answer it, thank you very much.
The question was translated from Hebrew. So I have no source for the question.