2016/07/21 by Saleh Soltan, Mihalis Yannakakis, Soltan, Saleh +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1607.06509
openalex publication_date 2016/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (V1,V2) such that G[V1] and G[V2] are connected, |p(V1)|,|p(V2)|≤ cp, and max\(|V1|)/(|V2|),(|V2|)/(|V1|)\≤ cs, for some constants cp and cs. When G is 2-connected, we show that a solution with cp=1 and cs=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(V1)=p(V2)=0 and |V1|=|V2|, 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.