1
$\begingroup$

Given a graph $G = (V, E)$ and a natural number $k$, consider the problem of determining whether there is a way to color the vertices with two colors in such a way that at least $k$ edges are polychromatic.

Prove that this problem is NP-complete.

I thought about reducing it to the 3-colorability problem, but I can't figure out a possible transformation that would work.

Any leads?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Depends what you mean. Literally, it's the same thing as having at most $m-k$ monochromatic edges, where $m$ is the total number of edges. But, in complexity terms, it doesn't matter whether you call that number $m-k$ or $k'$ or just $k$. $\endgroup$ – David Richerby Dec 7 '17 at 15:01
1
$\begingroup$

A simpler reduction is from MAX-CUT. The idea is to represent each edge as a gadget which is a complete bipartite graph having $N$ vertices on each side. By choosing $N$ large enough, we can force any potential coloring to color all vertices on one side using color 1, and all vertices on the other side using color 2. You can now connect these gadgets in such a way that the maximum number of bichromatic edges is closely related to the maximum cut in the original graph.

I'll let you work out the details.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ It's actually identical to my problem. All the edges in the cut correspond to the clauses that contain both true and false variables. Thank you! $\endgroup$ – Billy Joel Dec 7 '17 at 21:39
  • 1
    $\begingroup$ That is of course by a reduction from the MAX-2-colorability problem. $\endgroup$ – Billy Joel Dec 7 '17 at 21:41

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.