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 →{−1, +1} satisfying  p ( V )=Σ  j ∈ v    p ( j )=0. The objective is to partition  G  into ( V  1 ,  V  2 ) such that  G [ V  1 ] and  G [ V  2 ] are connected, | p ( V  1 )|, | p ( V  2 )|≤ c p  , and max [EQUATION], for some constants  c p   and  c s  . When  G  is 2-connected, we show that a solution with  c p  =1 and  c s  =3 always exists and can be found in polynomial time. 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 | V  1 |=| V  2 |, if | V |≡0(mod 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 ±1), and to the case that  p ( V )≠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.
['Saleh Soltan', 'Mihalis Yannakakis', 'Gil Zussman']
Doubly balanced connected graph partitioning