Doubly Balanced Connected Graph Partitioning

We introduce and study the Doubly Balanced Connected graph Partitioning (DBCP) problem: Let $G=(V,E)$ be a connected graph with a weight (supply/demand) function $p:V\to \{-1,+1\}$ satisfying $p(V)=\sum_{j\in V} p(j)=0$\mathrm{.}Theobjectiveistopartition$G$into$(V_1,V_2)$suchthat$G[V_1]$and$G[V_2]$areconnected,$|p(V_1)|,|p(V_2)|\leq c_p$,and$\max{\frac{|V_1|}{|V_2|},\frac{|V_2|}{|V_1|}}\leq c_s$,forsomeconstants$c_p$and$c_s$\mathrm{.}When$G$is2-connected,weshowthatasolutionwith$c_p=1$and$c_s=3$alwaysexistsandcanbefoundinpolynomialtime\mathrm{.}Moreover,when$G$ is 3-connected, we show that there is always a `perfect’ solution (a partition with $p(V_1)=p(V_2)=0$ and $\mathrm{\mid }{V}_1\mathrm{\mid }=\mathrm{\mid }{V}_2\mathrm{\mid }$, if $|V|\equiv 0 ($\mathrm{m}\mathrm{o}\mathrm{d}$~4)$), and it can be found in polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily $\pm 1$), and to the case that $p(V)\mathrm{\ne }0$ and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types.