2021/08/23 by Phablo F. S. Moura, Moura, Phablo F. S., Matheus J. Ota +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2108.10398
openalex publication_date 2021/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Partitioning a connected graph into k~vertex-disjoint connected subgraphs of similar (or given) orders is a classical problem that has been intensively investigated since late seventies. Given a connected graph G=(V,E) and a weight function w : V → ℚ_≥, a connected k-partition of G is a partition of V such that each class induces a connected subgraph. The balanced connected k-partition problem consists in finding a connected k-partition in which every class has roughly the same weight. To model this concept of balance, one may seek connected k-partitions that either maximize the weight of a lightest class (max-min BCPk) or minimize the weight of a heaviest class (min-max BCPk). Such problems are equivalent when k=2, but they are different when k≥ 3. In this work, we propose a simple pseudo-polynomial (k)/(2)-approximation algorithm for min-max BCPk which runs in time O(W|V||E|), where W = ∑v ∈ V w(v). Based on this algorithm and using a scaling technique, we design a (polynomial) ((k)/(2) +ε)-approximation for the same problem with running-time O(|V|3|E|/ε), for any fixed ε>0. Additionally, we propose a fixed-parameter tractable algorithm based on integer linear programming for the unweighted max-min BCPk parameterized by the size of a vertex cover.