2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand ... Why not color all vertices with $1$ and what is $G'$? If all vertices are labeled 0 (as you say), then the sum will be 0. Also, "reverse 3-coloring problem where the neighbors have to have matched color" sounds like you simply want to color all vertices with the same color. $\endgroup$ – Pål GD May 11 '13 at 7:32
  • $\begingroup$ The OP wants to recolor the vertices with color 0 (which represents the state "unknown") to match many of its neighbors (if the weights are 1). Can you add a small example to show where a greedy strategy fails? $\endgroup$ – frafl May 11 '13 at 9:47
  • $\begingroup$ Thanks, @frafl, missed that. So if $G' =G$, it is trivial. So you want to partition the vertices into sets such that the sum of weight of the edges going between partitions, minus the weight of the edges going inside the partitions is maximized. $\endgroup$ – Pål GD May 11 '13 at 11:27
  • $\begingroup$ @PålGD, essentially the idea is to label vertices in the subset $G'$ in way that it clashes well with vertices that are neighbors. Maximizing $G'$ is the same as maximizing whole $G$ because $G-G'$ remains unchanged. $\endgroup$ – 372 May 11 '13 at 16:07
  • $\begingroup$ @frafl, do you think this is uber hard problem ? Although I can't figure it out right now, I did get surprised that the community has nothing to offer.Does this mean that problem is very difficult ? Is there a way to tell at whether at least it is NP-Complete problem ? Thank you $\endgroup$ – 372 May 12 '13 at 16:46
1
$\begingroup$

Hint: Your problem looks a lot like minimum $(s,t)$-cut.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.