Approximating the maximally balanced connected partition problem in graphs

The approximability of the following optimization problem is investigated: Given a connected graph G = (V, E), find the maximally balanced connected partition for G, i.e. a partition (V1, V2) of V into disjoint sets V1 and V2 such that both subgraphs of G induced by V1 and V2 are connected, and maximize an objective function “balance”, B(V1, V2) = min(¦V1¦, ¦V2¦). We prove that for any ϵ > 0 it is NP-hard (even for bipartite graphs) to approximate the maximum balance of the connected partition for G = (V, E) with an absolute error guarantee of ¦V¦1 − ε. On the other hand, we give a polynomial-time approximation algorithm that solves the problem within 43 even when vertices of G are weighted. The variation of the problem is equivalent to the Maximally Balanced Spanning Tree Problem studied by Galbiati, Maffioli and Morzenti (1995). Our simple polynomial-time algorithm approximates the solution of that problem within 1.072.