<p>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 <em>maximal</em>, where $w(G')$ is the sum of vertex weights in $G'$.</p>

<p>I know that the problem of <em>minimizing</em> $|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 <em>maximizing</em> version? Even a heuristic algorithm without proof of approximation bound would be helpful.</p>

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

CC BY-SA 3.0
2017-11-27T05:47:39.313Z
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.
jcai
CC BY-SA 3.0
2017-11-27T12:22:35.843Z
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$?
domotorp
<graph-theory><graph-algorithms><approximation-algorithms><partition-problem>
Unbalanced connected partition
jcai
# Unbalanced connected partition

(Asked by: username_0 on 2017-11-26)

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

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, partition-problem

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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$?  

---

## 0 answers

