Return to Revisions

The problem you asked is the unweighted version of the Balance Connected 2-Partition (BCP_2). For unweighted case, any 2-connected graph can be partitioned into two connected subgraphs whose numbers of vertices differ by at most one. A simple algorithm uses st-numbering. For any 2-connected graph, we can label the vertices by [1..n] such that any vertex has simultaneously a neighbor with smaller label and a neighbor with larger label. Let V_1={1..n/2} and V_2=V-V_1. It can be easily shown that both V_1 and V_2 induce connected subgraphs. However, when there are cut vertices, the problem is NP-hard because it is equivalent to the weighted BCP_2. The transformation is as follows. Let v be a cut vertex and H be the maximum connected component in G-v. We shrink all components other than H into v and the weight of v is given by the weight of the vertices combined in v. Repeat this process and we can obtain a weighted 2-connected graph. It can be easily realized that there exists a graph such that the minimum part contains only n/3 vertices in any 2-partition.
For BCP_2, the currently best approximation algorithm is due to Chlebikova (I hope that it is not out of date): Approximating the maximally balanced connected partition problem in graphs, Information Processing Letters, 60:225--230, 1996. The approximation ratio is 4/3. For some special graphs, there are better results. For example, FPTAS for interval graphs and 5/4-approximation for grid graphs (further improved to 7/6).