Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they have the same color.)

I want to prove the above problem is NP-complete. Call the above problem P1.

Answer: I am trying to reduce the k-coloring problem.

P2: Given a graph $G=(V,E)$ and set of colors $k<V$ is the graph k-colorable (zero conflicts)?

P2 is feasible iff P1 has optimal value is exactly $0$. Therefore if P1 is solved we know solution to P2.

Is this solution correct? Is it what is suggested by the first comment of user G.Bach in A variation of the graph coloring problem ?

  • $\begingroup$ This is the idea, but you need to be more formal and present the many-to-one reduction from $k$-coloring to your problem. $\endgroup$ Mar 4 '14 at 2:17
  • $\begingroup$ "Therefore if P2 is solved we know solution to P2." - Did you mean P1 somewhere here? $\endgroup$ Mar 4 '14 at 2:17
  • $\begingroup$ @YuvalFilmus Sorry for the typo, it should be "Therefore if P1...". Could you please explain what you mean by " be forma and present many-to-one reducion"? $\endgroup$
    – Mat
    Mar 4 '14 at 2:26
  • $\begingroup$ I take issue with the sentence "Therefore if P1 is solved we know solution to P2". This is intuition. NP-hardness is a precise concept. You have the right idea, you just need (for this course) to present it more formally. You need to come up with a many-one reduction from graph coloring to your problem. This reduction is what you mean by "P2 is feasible iff P1 has optimal value exactly 0". The conclusion should then be that your problem is NP-hard by some theorem you proved in lecture. $\endgroup$ Mar 4 '14 at 3:11
  • $\begingroup$ @YuvalFilmus I am not taking any courses. I'm doing self studying for my thesis. Can I say: An instance of P2 has a solution iff P1 problem has value $0$. The objective function of P1 has "0" in its range. Therefore since P2 is NP-complete P1 is also NP-complete. Is this correct? $\endgroup$
    – Mat
    Mar 4 '14 at 3:28

First of all, you haven't formulated your problem as a decision problem (a problem that has a YES/NO answer). The decision problem corresponding to your optimization problem is: Given a graph $G$, an integer $k$ and another integer $\ell$, is there a $k$-coloring of $G$ with at most $\ell$ monochromatic edges?

In order to show NP-completeness of a problem $P$, you need to do two things:

  1. Show that $P$ is in NP. This is usually easy. It just means that a putative solution can be verified.
  2. Show that $P$ is NP-hard. In practice, this is (almost) always done by showing that some other NP-hard problem $Q$ is many-one reducible to $P$. This implies that $P$ itself is NP-hard.

A many-one reduction from $Q$ to $P$ is a function $f$, computable in polynomial time, which maps an instance $x$ of $Q$ to an instance $f(x)$ of $P$ such that $x \in Q$ iff $f(x) \in P$.

In your case, it is easy to see that your problem (let's call it MIN-MONOCHROMATIC) is in NP: the NP machine guesses a $k$-coloring of $G$, and verifies (in polynomial time) that there are at most $\ell$ monochromatic edges. In order to show that it is NP-hard, we come up with a many-one reduction $f$ from the NP-hard problem K-COLORING to MIN-MONOCHROMATIC. The reduction $f$ takes a graph $G$ and an integer $k$, forming an instance of K-COLORING, to the instance $(G,k,0)$ of MIN-MONOCHROMATIC (i.e., with $\ell=0$). The definition of coloring implies that $(G,K)$ is in K-COLORING iff $(G,k,0)$ is in MIN-MONOCHROMATIC. Also, clearly $f$ can be computed in polynomial time. So $f$ is a polytime many-one reduction from an NP-hard problem K-COLORING to MIN-MONOCHROMATIC, so we conclude that the latter is NP-hard. Since it is also in NP, it is NP-complete.

As you see, this is the same proof as yours, only with a lot of fluff. At this stage of your education, this fluff is important, since you need to makes sure that you understand the definitions not only intuitively but also formally (both are important). Once you're past this stage, all the details you really need are the ones explained in your current proof.

  • $\begingroup$ I will use this in my research so I will acknowledge you. Thanks a lot, very clear. $\endgroup$
    – Mat
    Mar 4 '14 at 12:21
  • $\begingroup$ One question, if you could please explian. You seem to prove the decision problem is NP-hard what about the optimization problem? My original problem is asking for $\min l$. $\endgroup$
    – Mat
    Mar 4 '14 at 14:05
  • 3
    $\begingroup$ NP-hardness is a category applying to decision problems. Optimization problems cannot be any more NP-hard than cows. If the corresponding problem is NP-hard, then this provides strong evidence that the optimization problem cannot be solved exactly in polynomial time. Beyond that, we have approximation algorithms and hardness of approximation. $\endgroup$ Mar 4 '14 at 14:33
  • $\begingroup$ Got it finally :) thanks a lot. Like the part with the cows LOL $\endgroup$
    – Mat
    Mar 4 '14 at 14:34
  • $\begingroup$ Then why do people say integer programming is NP-hard? Is it because the decision problem is NP-hard? $\endgroup$
    – Mat
    Mar 4 '14 at 14:56

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.