战略顶点标签

Question

我们获得了一个图形$ g =（v，e）$，带正边缘$ w_ {i} $和数值{0,1，-1}标签$ l $用于所有顶点。我们知道，$ g $具有标记为0的所有顶点的子集$ g'$，问题是将标签分配给$ g'$的顶点，以使此总和最大化$ sum_ {e_ {e_ {e_ {u，v } in E} w_ {i} l_ul_v。$问题是此问题是否为NP complete。如果不是，那么多项式算法是什么？

我个人认为，这个问题本质上是三色的一种形式。挑战是根据邻居选择标签{1，-1}。假设$ g $和$ g'$之间的边界有很多1秒，那么最好选择1 $ g'$的顶点标签，同样，如果边界有很多-1标签的-1是因为$ -1*-1 = 1 $。因此，从本质上讲，这成为邻居必须具有匹配颜色的某种反向三色问题。

您能帮助将这个问题减少到3色（或反之亦然）吗？也许有多项式时间算法？

Answer 1

提示：您的问题看起来很像最低$（S，T）$ - 切割。