An Improved Approximation Algorithm for the Minimum 4-Star Partition Problem
Qilu Bao, Wei Yu, Zhaohui Liu, Yong Chen · International Journal of Foundations of Computer Science · 2025
In this paper, we investigate the minimum k-star partition problem (Min-kSP for short) in which we are given an undirected graph and the objective is to compute a minimum number of vertex-disjoint stars containing at most k vertices such that all the vertices are covered by these stars. We design a [Formula: see text]-approximation algorithm for the Min-4SP based on the local search method, which improves on the previous 2-approximation algorithm implied by the results in the literature. Our algorithm starts with a feasible solution containing the minimum number of singletons, i.e. stars containing a single vertex, and then iteratively applies four local search operations to reduce the number of stars. When no improvements is possible, the algorithm terminates and outputs the current solution.