Approximation Algorithm for the Balanced 2-Connected Bipartition Problem

For two positive integers m, k and a connected graph G = (V, E) with a nonnegative vertex weight function w, the balanced m-connected k-partition problem, denoted as BCmPk, is to find a partition of V into k disjoint nonempty vertex subsets (V-1, V-2, ..., V-k) such that each G[V-i] (the subgraph of G induced by Vi) is m-connected, and min(1 <= i <= k){w(V-i)} is maximized. In this paper, we study the BC2P2 problem on 4-connected interval graphs. First, a 3/2-approximation algorithm is given. Then, assuming that w is integral, a fully polynomial time approximation scheme (FPTAS) is obtained. As far as we known, this is the first paper studying balanced connected partition problem with higher connectivity requirement on each part.