2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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

0

Reset to default

Your Answer

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