Strategic vertex labeling

Question

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 ?

Answer 1

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, e.g., use the Ford-Fulkerson algorithm.

Answer 2

Unless I misread your question, your problem is identical to maximum cut when $G'=G$, implying your problem is NP-hard.

(Actually, as David Benson-Putnins points out, I did misread the question. My answer requires the edge weights to be not necessarily positive.)

Answer 3

Some observations which are too long for a comment to simplify the problem. The edges that are do not connect to G' are irrelevant, as is every 0 vertex that is outside of G'. So we can throw those away. If a vertex in G' has some 1s and some -1s, then we know that if we make it a 1 we get the sum of the weights to the 1s - weights to (-1)s, and if we make the G' vertex a -1 we get negative that contributed to the sum. So we can throw away G entirely and we have a graph G' with weights $w_{ij} > 0$ for each edge, and weights $v_k$ of any sign for each vertex and we want to maximize

$ \sum_{i,j} w_{ij} l_i l_j + \sum_{k} v_k l_k$

This is resistant to a greedy algorithm attempt. For example suppose that I have twelvevertices, which I will label $a$ and $b_1,...b_{11}$. My objective is to pick each $l_j$ one at a time to maximize the sum given the other $l_j$s. I'll call the labels $l_a$ and $l_1,..,l_{11}$. If $v_a = 10$ and $v_j = -1$ for each $j$, and $w_{aj} = 1.001$ for each $j$, and there are no other edges, then the first thing you would do is assign $l_a = 1$. After that, assigning $l_j=1$ increases the sum by .001, and making it a $-1$ decreases it by .01, so you would make each $l_j = 1$ and the total sum would be 10.01.

But if I had instead assigned each vertex a $-1$ labeling, my total sum would be 11.01. Also the greedy algorithm solution of all 1s is resistant to changing a single vertex, so trying to solve this on a local level is probably impossible