Approximation and Inapproximability Results on Balanced Connected Partitions of Graphs

Abstract

Let $G=(V,E)$ be a connected graph with a weight function $w: V o mathbb{Z_+}$, and let $q geq 2$ be a positive integer. For $Xsubseteq V$, let $w(X)$ denote the sum of the weights of the vertices in $X$. We consider the following problem on $G$: find a $q$-partition $P=(V_1,V_2, ldots, V_q)$ of $V$ such that $G[V_i]$ is connected ($1leq ileq q$) and $P$ maximizes ${ m min}{w(V_i): 1leq ileq q}$. This problem is called extit{Max Balanced Connected $q$-Partition} and is denoted by BCP$_q$. We show that for $qgeq 2$ the problem BCP$_q$ is NP-hard in the strong sense, even on $q$-connected graphs, and therefore does not admit a FPTAS, unless ${ m P}={ m NP}$. We also show another inapproximability result for BCP$_2$ on arbitrary graphs. On $q$-connected graphs, for $q=2$ the best result is a $frac{4}{3}$-approximation algorithm obtained by Chleb'{i}kov{'a}; for $q=3$ and $q=4$ we present $2$-approximation algorithms. When $q$ is not fixed (it is part of the instance), the corresponding problem is called extit{Max Balanced Connected Partition}, and denoted as BCP. We show that BCP does not admit an approximation algorithm with ratio smaller than $6/5$, unless ${ m P}={ m NP}$.