approximation algorithms for maximally balanced connected graph partition

• DOI: 10.48550/arxiv.1910.02470
• Publication Date: 2019-01-01
• Authors: Yong Chen; Zhi-Zhong Chen; Guohui Lin; Yao Xu; An Zhang
• Keywords: FOS: Computer and information sciences; Discrete Mathematics (cs.DM); Computer Science - Data Structures and Algorithms; 0211 other engineering and technologies; Data Structures and Algorithms (cs.DS); 02 engineering and technology; Computer Science - Discrete Mathematics

Given a simple connected graph $G = (V, E)$, we seek to partition the vertex set $V$ into $k$ non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these $k$ parts is minimized. We refer this problem to as {\em min-max balanced connected graph partition} into $k$ parts and denote it as {\sc $k$-BGP}. The general vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm; the vertex-weighted {\sc $2$-BGP} and {\sc $3$-BGP} admit a $5/4$-approximation and a $3/2$-approximation, respectively; but no approximability result exists for {\sc $k$-BGP} when $k \ge 4$, except a trivial $k$-approximation. In this paper, we present another $3/2$-approximation for our cardinality {\sc $3$-BGP} and then extend it to become a $k/2$-approximation for {\sc $k$-BGP}, for any constant $k \ge 3$. Furthermore, for {\sc $4$-BGP}, we propose an improved $24/13$-approximation. To these purposes, we have designed several local improvement operations, which could be useful for related graph partition problems.<br/>23 pages, 7 figures, accepted for presentation at COCOA 2019 (Xiamen, China)<br/>