Balanced connected partitions of graphs: approximation, parameterization and lower bounds

A connected k-partition of a graph is a partition of its vertex set into k classes such that each class induces a connected subgraph. Finding a connected k-partition in which the classes have similar size is a classical problem that has been investigated since late seventies. We consider a more general setting in which the input graph $$G=(V,E)$$ G = ( V , E ) has a nonnegative weight assigned to each vertex, and the aim is to find a connected k-partition in which every class has roughly the same weight. In this case, we may either maximize the weight of a lightest class (max–min BCP $$_k$$ k ) or minimize the weight of a heaviest class (min–max BCP $$_k$$ k ). Both problems are $$\text {\textsc {NP}}$$ NP -hard for any fixed $$k\ge 2$$ k ≥ 2 , and equivalent only when $$k=2$$ k = 2 . In this work, we propose a simple pseudo-polynomial $$\frac{3}{2}$$ 3 2 -approximation algorithm for min–max BCP $$_3$$ 3 , which is an $$\mathcal {O}(|V ||E |)$$ O ( | V | | E | ) time $$\frac{3}{2}$$ 3 2 -approximation for the unweighted version of the problem. We show that, using a scaling technique, this algorithm can be turned into a polynomial-time $$(\frac{3}{2} +{\varepsilon })$$ ( 3 2 + ε ) -approximation for the weighted version of the problem with running-time $$\mathcal {O}(|V |^3 |E |/ {\varepsilon })$$ O ( | V | 3 | E | / ε ) , for any fixed $${\varepsilon }>0$$ ε > 0 . This algorithm is then used to obtain, for min–max BCP $$_k$$ k , $$k\ge 4$$ k ≥ 4 , analogous results with approximation ratio $$(\frac{k}{2}+{\varepsilon })$$ ( k 2 + ε ) . For $$k\in \{4,5\}$$ k ∈ { 4 , 5 } , we are not aware of algorithms with approximation ratios better than those. We also consider fractional bipartitions that lead to a unified approach to design simpler approximations for both min–max and max–min versions. Additionally, we propose a fixed-parameter tractable algorithm based on integer linear programming for the unweighted max–min BCP parameterized by the size of a vertex cover. Assuming the Exponential-Time Hypothesis, we show that there is no subexponential-time algorithm to solve the max–min and min–max versions of the problem.