3
$\begingroup$

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.

Constraints:

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

Improve this question
$\endgroup$
2
  • 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$
    – Rajarshi basu
    Nov 17, 2021 at 12:24

0

Reset to default

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.