Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are connected and such that $|w(G')-w(G'')|$ is maximal, where $w(G')$ is the sum of vertex weights in $G'$.

I know that the problem of minimizing $|w(G')-w(G'')|$ is called Balanced Connected Partition for $k=2$, or $BCP_2$, with vertex weights. Chlebikova in 1996 showed that this admits a poly-time $4/3$-approximation algorithm. Is there also literature for the maximizing version? Even a heuristic algorithm without proof of approximation bound would be helpful.

Actually, the ultimate problem I am trying to solve is a combination of these. If each vertex has two weights $w_1(v), w_2(v)$ then I wish to maximize $|w_1(G')-w_1(G'')| - |w_2(G') - w_2(G'')|$.

  • $\begingroup$ Yes, I should have clarified: negative weights are allowed (for the problem of maximizing imbalance), otherwise it would indeed be trivial. Thus for the second question, the $w_1(v)$ may be negative, but $w_2(v) \geq 0$ may be assumed. $\endgroup$ – Arcinde Nov 27 '17 at 5:47
  • $\begingroup$ Given $s\in G$, what is the complexity of deciding whether there is a connected $S$ for which $s\in S$ and $w(S)>0$? $\endgroup$ – domotorp Nov 27 '17 at 12:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.