Approximation algorithm for the balanced 2-connected k-partition 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 BC m P k, 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 V i ) is m-connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G, k ), that is, β m ⁎ ( G, k ) = max ⁡ min 1 ≤ i ≤ 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 2k-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 β 2 ⁎ ( G, k ) ≥ W / ( 2 k − 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 BC 2 P k problem on 2k-connected interval graphs.

Authors

• Di Wu Hunan University ExponentiAI Innovation
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering
• Weili Wu

Keywords

• Balanced m-connected k-partition
• Interval graph
• Pseudo-polynomial time algorithm
• FPTAS