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$
    – jcai
    Nov 27, 2017 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, 2017 at 12:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.