Fully Polynomial Time Approximation Algorithm For Balanced Connected K-partition On Trapezoid Graph

For a connected graph G=（V, E） and a positive integral vertex weight function w,a max-min weight balanced connected k-partition of G, denoted as BCPk, is a partitionof V into k disjoint vertex subsets （V₁, V₂,..., V_k） such that each G[Vi]（the subgraph ofG induced by Vi） is connected, and min1≤i≤k{w（Vi）} is maximum. Such a problem hasa lot of applications in image processing and clustering analysis, and was proved to beNP-hard. In this paper, we study BCPkon a special class of graphs: trapezoid graphswhose maximum degree is bounded by a constant. A pseudo-polynomial time algorithmis given, based on which a fully polynomial time approximation algorithm is obtainedfor k=2,3,4. A step-stone for the analysis of the fully polynomial time approximationalgorithm depends on a lower bound for the optimal value of BCPkabout the totalweight of the graph. In providing such a lower bound, we get the following result: any4-connected trapezoid graph on at least7vertices has a4-contractible edge, which mayhave a value in the field of graph theory.