Strategic vertex labeling

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 ?

• The options are not NP-complete and P. There are plausible candidates for problems of intermediate difficulty, e.g. factoring. – Qiaochu Yuan May 13 '13 at 3:34

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.

• @Dustin G. Mixon, do you think it is possible to set up flows and capacities in such way that F-F algorithm becomes usable ? – 372 May 13 '13 at 22:38
• You should be able to treat each edge $ij$ as a pair of directed edges in opposite directions, each with capacity $w_{ij}$. Does that make sense? – Dustin G. Mixon May 14 '13 at 3:20

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

• @Dustin G. Mixon, thank you for your input. Although on the surface the max-cut seems to be similar, in reality the problems are quite different. The challenge in the problem I posted is to chose values of nodes on any given edge such that the product of such values $l_u l_v$ stays non-negative. Since we have boundary between $G$ and $G'$ such that edges intersected by the boundary on the side of $G'$ have nodes with values 0 and on the side of $G$ with have values{0,-1,1} the challenge is to relabel the 0s on the side of $G'$ in such way that product of labels on both sides maximizes the sum – 372 May 12 '13 at 18:12
• Joseph this comment confused me a little.. from your original post I would have thought that G' had ALL the vertices with weight 0, but from the comment it sounds like G' only contains some of them, and some might be left in G. I'm not sure if it makes a difference in the problem since any leftover 0 vertices can just be ignored but I wanted to check which interpretation is correct – David Benson-Putnins May 12 '13 at 18:29
• @David Benson-Putnins, My apologies for possible misrepresentation. Set $G'$ indeed contains only vertices with values 0, however, intuitively speaking, the vertices that are close to the boundary have edges that reach out to the $G-G'$ where vertices can have labels from {0,-1,1}. So yes, vertices in $G-G'$ can have any value(either 0, 1 or -1) – 372 May 12 '13 at 18:40
• @Joseph: You should edit your question then. Make it clear that $G'$ is a subset of the $0$-vertices, and that the sum is not over all edges, but rather over the boundary of $G'$. Note that if the sum were over all edges, then my answer would be correct. – Dustin G. Mixon May 12 '13 at 18:54
• @Dustin G. Mixon, you are right, the problem did not say it clearly that $G'$ has all 0 and my previous comment is wrong. $G-G'$ contains only {1,-1}. – 372 May 12 '13 at 20:01

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