Discrete Mathematics & Theoretical Computer Science, Vol 9, No 1 (2007)

Font Size:  Small  Medium  Large

Approximation and Inapproximability Results on Balanced Connected Partitions of Graphs

Yoshiko Wakabayashi, Frédéric Chataigner, Liliane Benning Salgado


Let $G=(V,E)$ be a connected graph with a weight function $w: V \to \mathbb{Z_+}$, and let $q \geq 2$ be a positive integer. For $X\subseteq 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 ($1\leq i\leq q$) and $P$ maximizes ${\rm min}\{w(V_i): 1\leq i\leq q\}$. This problem is called \textit{Max Balanced Connected $q$-Partition} and is denoted by BCP$_q$. We show that for $q\geq 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 ${\rm P}={\rm 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 \textit{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 ${\rm P}={\rm NP}$.

Full Text: PDF PostScript