We are given a graph $G=(V,E)$ with positive edge weights $w\_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with 0 in $G$ are considered to in the subset called $G'$). The problem is to assign labels to the vertices in $G'$ in such way that this sum is maximized $\sum\_{e\_{u,v}\in E} w\_{i}l\_ul\_v.$ The question is whether this problem is NP-complete or not. If it is not then what is the polynomial algorithm?


Personally I believe that this problem is essentially a form of 3-Coloring. The challenge is to chose the labels {1,-1} depending on the neighbors. Say the boundary between $G$ and $G'$ has a lot of 1s or 1s then it is better to chose 1s for the labeling of vertices in $G'$, similarly if the boundary has lots of -1s then it is better to chose -1s for labeling because $-1\*-1=1$. So essentially this becomes some sort of reverse 3-Coloring problem where the neighbors have to have matched color.


Can you help reduce this problem to 3-Coloring (or vice-versa) ? Or perhaps there is polynomial time algorithm ?



Strategic vertex labeling
Now that I think I understand your problem, I think I also know the solution: There exists a polynomial-time algorithm to solve your problem.


For the sake of clarity, I am re-writing the problem statement (as I am now interpreting it):


The vertices of $G$ are each labeled as $0$, $1$ or $-1$. Let $G'$ denote the $0$-vertices. The goal is to relabel the vertices of $G'$ with $1$s and $-1$s so as to maximize $\sum\_{ij\in E}w\_{ij}l\_il\_j$.


To solve this problem, I first combine all of the $1$-vertices in $G$ into a single vertex $s$ (labeled with a $1$), and the $(-1)$-vertices into $t$ (labeled with a $-1$). Note that in this new graph, every relabeling of $G'$ produces a partition of the vertices $V=S\sqcup T$, namely an $s$-$t$ cut. Furthermore, our objective function can be expressed in terms of the capacity of this cut: 


$$ \sum\_{ij\in E}w\_{ij}l\_il\_j = \sum\_{ij\in E}w\_{ij}-2C(S,T). $$


As such, your problem is equivalent to finding the $s$-$t$ cut of minimum capacity in this network, which you can do with the [max-flow min-cut theorem](http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem), e.g., use the [Ford-Fulkerson algorithm](http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm).


