3
$\begingroup$

I have a question from a test I did and failed, a question I failed to do.

In short:

the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined.

The new problem is called Min-Monochromatic. Want to show that this problem belongs to $NP$ , and later make a reduction from Edge-Coloring and Vertex-Coloring to it.

The question has three parts, all parts are related to each other. The first part, which is the easiest of the three I was able to do in my opinion.

The second part shows a reduction from Vertex-Coloring to Min-Monochromatic, ie $Vertex-Coloring \leq_p Min-Monochromatic$: I could not do that properly.

The third part should show a reduction from Edge-Coloring to Min-Monochromatic, i.e. $Edge-Coloring \leq_p Min-Monochromatic$ : I also could not do for the same reasons of the second part, and in addition the question is more complex, there is a reference between Edge-Coloring and Vertex- Coloring.

The question:

Let's look at the Min-Monochromatic problem. In this problem, we are given 3 things:

  • Undirected graph, G = (V, E).
  • Natural number $k \in \mathbb{N}$ so that $k> 0$.
  • Another natural number $l \in \mathbb{N}$ so that $l> 0$.

We are asked if there is a color function $\varphi : V\rightarrow \begin{Bmatrix} 0,\cdots,k-1 \end{Bmatrix}$ so that there are at most $l$ pairs of neighbors with the same color. Note that the color function $\varphi$ is not necessarily valid (in this problem we are allowed to have neighbors of the same color, the goal is only to minimize the number of cases). We want to show that the problem is NP-complete. We will see this in parts.

Part One:

Show that $Min-Monochromatic(G,k,l) \in NP$. You must explain the correctness of the validation algorithm and analyze the runtime.

My answer:

Given an instance $(G, k, l)$ of the Min-Monochromatic problem. The witness who is a subgroup $U \subseteq V$. Graph $G_U = (U,E_U)$ was built.

The validation algorithm will first count the different colors that the vertices in the graph have. If the number is less than or equal to k, we will continue.

After this we will define a counter c = 0. For each edge in the graph, if the color of the vertices to which it is connected is the same, we will increase the counter by 1.

If the counter is less than or equal to $ l $, we return true

The algorithm is polynomial, we will go through each edge and each vertex exactly once.

Part Two:

Show that $Min-Monochromatic$ is $NP-complete$. You must:

  • Build a reduction that will see it.
  • Prove its correctness.
  • Analyze the running time.

(Instruction: You can show $Vertex-Coloring \leq_p Min-Monochromatic$ reduction and assume that $Vertex-Coloring $ is NP-complete.)

My answer:

Here I could not continue. I was thinking of doing a reduction from $Min-Monochromatic$ to $Vertex-Coloring$ . You can add one more color, each time of adjacent vertices with the same color, delete the edge between them, and connect them to the new vertex. But in question they asked for the reduction and vice versa, so I could not continue.

Part Three:

Rely on the previous reduction and show $Edge-Coloring \leq_p Min-Monochromatic$.

You must:

  • Build a reduction that will see it.
  • Prove its correctness.
  • Analyze the running time.

In addition: Based solely on our conclusion from section B and this reduction, can it be determined to which class Edge-Coloring belongs? Explain and detail

My answer:

I think show reduction: $Edge-Coloring \leq_p Vertex-Coloring$.And because of the reduction from the second part it should work.

To show reduction from Edge-Coloring to Vertex-Coloring, it's not complicated.

Reduction from Edge-Coloring to Vertex-Coloring, creates a vertex for each edge, and creates an edge $(v_e, v_f)$ between each pair of different e and f edges that share a vertex.

In my opinion it is not possible to know only by the reduction in Part B to which class Edge-Coloring belongs. Because Edge-Coloring does not participate in this reduction at all.

I would be happy to help regarding the second and third part, which I could not understand properly, and the second part I could not do.

$\endgroup$
4
  • $\begingroup$ "The witness who is a subgroup $U \subseteq V$. Graph $G_U = (U,E_U)$ was built." I'm not sure what this is supposed to mean. You then analyze a coloring. Where does this coloring come from? Is this algorithm using non-determinism? $\endgroup$
    – idmean
    Jul 26 at 13:57
  • $\begingroup$ Thanks for the response, we have a G graph which is an instance of the Min-Monchromatic problem. The witness can give us a sub-graph of the graph G, give this graph I called $G_U$. Another thing, Vertex − Coloring is in my opinion k-coloring, was that what you meant when you asked where coloring came from? The k-coloring algorithm is in np, so it uses non-determinism $\endgroup$ Jul 26 at 14:11
  • $\begingroup$ Maybe I'm missing something, but I don't get what that new graph describes. A NTM to decide Min-Chromatic could 1. Guess a $\varphi$ of size $k$. 2. Iterate all edges and count the edges $(u, v)$ where $\varphi(u) = \varphi(v)$. 3. If the count $\leq l$ accept, otherwise reject. Is this what your algorithm does? $\endgroup$
    – idmean
    Jul 26 at 14:47
  • $\begingroup$ Yes exactly. You said it accurately. $\endgroup$ Jul 26 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.