Summary: 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 \(BC_m P_k\), is to find a partition of \(V\) into \(k\) disjoint nonempty vertex subsets \((V_1, V_2, \ldots, V_k)\) such that each \(G [V_i]\) (the subgraph of \(G\) induced by \(V_i\)) is \(m\)-connected, and \(\min_{1 \leq i \leq k} \{w(V_i) \}\) is maximized. The optimal value of \(BC_m P_k\) on graph \(G\) is denoted as \(\beta_m^\ast(G, k)\), that is, \(\beta_m^\ast(G, k) = \max \min_{1 \leq i \leq k} \{w(V_i) \}\), where the maximum is taken over all \(m\)-connected \(k\)-partition of \(G\). In this paper, we study the \(BC_2 P_k\) problem on interval graphs, and obtain the following results.
(1) For \(k = 2\), a 4/3-approximation algorithm is given for \(BC_2 P_2\) on 4-connected interval graphs.
(2) In the case that there exists a vertex \(v\) with weight at least \(W / k\), where \(W\) is the total weight of the graph, we prove that the \(BC_2 P_k\) problem on a 2\(k\)-connected interval graph \(G\) can be reduced to the \(BC_2 P_{k - 1}\) problem on the \((2 k - 1)\)-connected interval graph \(G - v\). In the case that every vertex has weight at most \(W / k\), we prove a lower bound \(\beta_2^\ast(G, k) \geq W /(2 k - 1)\) for 2\(k\)-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 \(BC_2 P_k\) problem on 2\(k\)-connected interval graphs.