1
$\begingroup$

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}$

  1. k
  2. 3k
  3. k^2
  4. |V|+1
  5. 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?

  1. yes.
  2. No, the amount of edges may be quadratic as a function of the amount of vertices.
  3. No, the amount of edges may be exponential as a function of the amount of vertices.
  4. You can not tell, depending on the size of the graph
  5. 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?

  1. Yes, reduction correct and well defined
  2. Although the reduction is correct, but it does not deal with cases where the original graph G was empty (without edges)
  3. 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.
  4. No
  5. 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.

$\endgroup$
3
  • $\begingroup$ Related cs.stackexchange.com/questions/142478/… $\endgroup$
    – Juho
    Jul 22 at 8:32
  • $\begingroup$ Related: cs.stackexchange.com/q/142590/755 $\endgroup$
    – D.W.
    Oct 26 at 3:39
  • $\begingroup$ You can still credit the original source: e.g., a book, a specific class, a web page. Nothing about translating from another language prevents you from crediting your sources. $\endgroup$
    – D.W.
    Oct 26 at 3:39
2
$\begingroup$

To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $G$ of Edge-Coloring has a solution precisely when the instance $G'$ of Vertex-Coloring has a solution.

Let's consider the questions A, B and C:

  • Question A: You should have a look at my answer to question C here first. Your intuition looks promising, but you should formalize (i.e., prove) it.

  • Question B: You are correct, the reduction is easily doable in polynomial time.

  • Question C: The construction is describing the construction of the line graph of $G$. Your task is to prove that $G$ has an edge $k$-coloring if and only if $G'$ has a vertex $k$-coloring. Do this in two parts: given an edge $k$-coloring of $G$, show how you can build a vertex $k$-coloring for $G'$. Then show the reverse direction, i.e., that a vertex $k$-coloring for $G'$ gives you an edge $k$-coloring for $G$. This is a good exercise, so I won't ruin (all) the details for you. Hint: in the first direction, start by giving the vertices $x_e$ the color on $e$. In the reverse reduction, what can you say about the coloring if you restrict it to the vertices $x_e$, i.e., what does this imply for the edges $e$ in $G$?

If you feel stuck, look at examples of some other reductions to get the idea.

$\endgroup$
2
  • $\begingroup$ I think I was able to prove it, and it turned out that the reduction is correct, I tried to produce all kinds of graphs, and each time I managed to paint the 2 types of graphs in the same k colors. Formally I could not prove, I did not find a source in the books and on the Internet. I think the reduction is correct and it is possible to paint both graphs in k colors, am I right? $\endgroup$
    – anihaham
    Jul 22 at 13:38
  • 1
    $\begingroup$ @anihaham Here's the proof that if $G$ can be edge-colored in $k$ colors, then $G'$ can be vertex-colored in $k$ colors. Let $c$ be a proper edge $k$-coloring. Our goal is to build a proper vertex-coloring using $k$ colors, say $c'$. My hint says that let's make $c'$ so that $c'(x_e) = c(e)$, i.e., we assign the color from the edge in $G$ to the corresponding vertex of $G'$. By construction, any vertex $v$ in $G'$ is adjacent precisely to the edges it's incident to in $G$ and these are all colored in distinct colors. Thus, $v$ is colored distinctly from its neighbors and we are done. $\endgroup$
    – Juho
    Jul 22 at 14:01

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.