主观题：Min-monochromatic edges problem

**Min-monochromatic edges problem:** Given a graph $$G=(V,E)$$ and a set of  $$2
答案：1. The decision problem is: Given a graph $$G$$, an integer $$k$$ and another integer $$l$$, is there a $$k$$-coloring of $$G$$ with at most $$l$$ monochromatic edges?

2. Show that a solution can be verified in polynomial time: for any $$k$$-coloring of $$G$$, it is easy to verify (in polynomial time) that there are at most $$l$$ monochromatic edges.

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