Approximation algorithm for the balanced 2-connected k-partition problem

For two positive integers m,km,k and a connected graph G=(V,E)G=(V,E) with a nonnegative vertex weight function w, the balanced m-connected k  -partition problem, denoted as BCmPkBCmPk, is to find a partition of V into k   disjoint nonempty vertex subsets (V1,V2,…,Vk)(V1,V2,…,Vk) such that each G[Vi]G[Vi] (the subgraph of G   induced by ViVi) is m  -connected, and min1≤i≤k⁡{w(Vi)}min1≤i≤k⁡{w(Vi)} is maximized. The optimal value of BCmPkBCmPk on graph G   is denoted as βm⁎(G,k), that is, βm⁎(G,k)=max⁡min1≤i≤k⁡{w(Vi)}, where the maximum is taken over all m-connected k-partition of G  . In this paper, we study the BC2PkBC2Pk problem on interval graphs, and obtain the following results.(1) For k=2k=2, a 4/3-approximation algorithm is given for BC2P2BC2P2 on 4-connected interval graphs.(2) In the case that there exists a vertex v   with weight at least W/kW/k, where W   is the total weight of the graph, we prove that the BC2PkBC2Pk problem on a 2k-connected interval graph G   can be reduced to the BC2Pk−1BC2Pk−1 problem on the (2k−1)(2k−1)-connected interval graph G−vG−v. In the case that every vertex has weight at most W/kW/k, we prove a lower bound β2⁎(G,k)≥W/(2k−1) for 2k-connected interval graph G.(3) Assuming that weight w   is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC2PkBC2Pk problem on 2k-connected interval graphs.