A greedy heuristic for a minimum-weight forest problem

Given an undirected edge-weighted graph and a natural number m, the authors consider the problem of finding a minimum-weight spanning forest such that each of its trees spans at least m vertices. For m≥4, the problem is shown to be NP-hard. The authors describe a simple 2-approximate greedy heuristic that runs within the time needed to compute a minimum spanning tree. If the edge weights satisfy the triangle inequality, any such a 2-approximate solution, in linear time, can be converted into a 4-approximate solution for the problem of covering the graph with minimum-weight disjoint cycles of size at least m.