A GREEDY HEURISTIC FOR A MINIMUM-WEIGHT FOREST PROBLEM

Given an undirected edge-weighted graph and a natural number m, we consider the problem of finding a minimum-weight spanning forest such that each of its trees spans at least m vertices. For m greater-than-or-equal-to 4, the problem is shown to be NP-hard. We 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 vertex disjoint cycles of size at least m.