I have a graph $G$ with $n$ nodes and $O(n)$ edges. Each of the nodes has a positive integral weight at least 2, such that sum of all weights is at most $O(n)$. We want to color the nodes and edges red or blue, where coloring a node of weight $C$ costs $C$ units, and coloring an edge costs 1 unit.


  • Any edge between two blue nodes must be blue
  • Any edge between two red nodes must be red

There are no constraints on edges between a red and a blue node.

Also given is we have exactly $R$ red and $B$ blue units of color, such that $R + B$ = sum of weights of nodes + edges. (Again, edges have weight 1.)

The problem is to determine whether the graph can be colored in a way that meets these constraints. Is this problem NP-complete? I suspect it is, but I am not sure which problem I can use to reduce this from.

  • 1
    $\begingroup$ If the sum could be n², you could reduce from sqrt-clique by having weights n and let R be $kn+{k \choose 2}$. $\endgroup$
    – Pål GD
    Nov 1, 2021 at 22:06
  • $\begingroup$ This does not work though, since we could end up coloring edges even if they are not from the clique $\endgroup$ Nov 17, 2021 at 12:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.