TY - JOUR
T1 - Approximation Algorithms for Maximally Balanced Connected Graph Partition
AU - Chen, Yong
AU - Chen, Zhi Zhong
AU - Lin, Guohui
AU - Xu, Yao
AU - Zhang, An
N1 - Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2021/12
Y1 - 2021/12
N2 - Given a 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 min-max balanced connected graph partition into k parts and denote it as k-BGP. The 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 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k≥ 3. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.
AB - Given a 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 min-max balanced connected graph partition into k parts and denote it as k-BGP. The 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 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k≥ 3. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.
KW - Approximation algorithm
KW - Connected component
KW - Graph partition
KW - Induced subgraph
KW - Local improvement
UR - http://www.scopus.com/inward/record.url?scp=85114815394&partnerID=8YFLogxK
U2 - 10.1007/s00453-021-00870-3
DO - 10.1007/s00453-021-00870-3
M3 - Article
AN - SCOPUS:85114815394
SN - 0178-4617
VL - 83
SP - 3715
EP - 3740
JO - Algorithmica
JF - Algorithmica
IS - 12
ER -