Doubly balanced connected graph partitioning

DOI10.1137/1.9781611974782.126zbMATH Open1410.05172arXiv1607.06509OpenAlexW2490403028MaRDI QIDQ4575873FDOQ4575873

Authors: Saleh Soltan, Mihalis Yannakakis, Gil Zussman 

Publication date: 16 July 2018

Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: 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:Vightarrow-1,+1$ satisfying $p(V)=su{m}_{jinV}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)|leq{c}_p$, and $maxfrac|V_1||V_2|,frac|V_2||V_1|leq{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 $|V_1|=|V_2|$, if $|V|equiv0(mathrmmod4)$), 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 $pm1$), and to the case that $p(V)eq0$ 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.

Full work available at URL: https://arxiv.org/abs/1607.06509

Recommendations

• Doubly balanced connected graph partitioning
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation algorithm for the balanced 2-connected \(k\)-partition problem
• scientific article; zbMATH DE number 4101263
• Approximation and inaproximability results on balanced connected partitions of graphs

zbMATH Keywords

graph partitioningpower grid islanding

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (10)

• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Mixed-integer programming techniques for the connected max-\(k\)-cut problem
• Reconfiguration of connected graph partitions via recombination
• Cardinality constrained connected balanced partitions of trees under different criteria
• Doubly balanced connected graph partitioning
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Title not available (Why is that?)
• Node-balancing by edge-increments
• Reconfiguration of connected graph partitions via recombination
• Approximation algorithms for the maximum bounded connected bipartition problem

This page was built for publication: Doubly balanced connected graph partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575873)