TY - GEN

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:
© 2019, Springer Nature Switzerland AG.

PY - 2019

Y1 - 2019

N2 - Given a simple connected graph, 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 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 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively; but no approximability result exists for k -BGP when, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality 3-BGP and then extend it to become a k/2-approximation for k -BGP, for any constant. Furthermore, for 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.

AB - Given a simple connected graph, 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 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 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively; but no approximability result exists for k -BGP when, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality 3-BGP and then extend it to become a k/2-approximation for k -BGP, for any constant. Furthermore, for 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.

KW - Approximation algorithm

KW - Connected component

KW - Graph partition

KW - Induced subgraph

KW - Local improvement

UR - http://www.scopus.com/inward/record.url?scp=85078565205&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-36412-0_11

DO - 10.1007/978-3-030-36412-0_11

M3 - Conference article

AN - SCOPUS:85078565205

SN - 9783030364113

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 130

EP - 141

BT - Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings

A2 - Li, Yingshu

A2 - Cardei, Mihaela

A2 - Huang, Yan

PB - Springer

T2 - 13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019

Y2 - 13 December 2019 through 15 December 2019

ER -