An Improved Approximation Algorithm for the Minimum 4-Star Partition Problem

In this paper, we investigate the minimum [Formula: see text]-star partition problem (Min-[Formula: see text]SP 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 [Formula: see text] 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.