US EPA

4822548 

Journal Article 

Doubly Balanced Connected Graph Partitioning 

Soltan, S; Yannakakis, M; Zussman, Gil; ACM 

2017 

1939-1950 

WOS:000426965800126 

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)=Sigma(j is an element of 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, vertical bar P(V-1)vertical bar, vertical bar P(V-2)vertical bar <= c(p), and max{vertical bar V-1 vertical bar/vertical bar V-2 vertical bar, vertical bar V-2 vertical bar/vertical bar V-1 vertical bar}<= c(s), 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 vertical bar V-1 vertical bar=vertical bar V-2 vertical bar, if vertical bar V vertical bar equivalent to 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)not equal 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.