The k-labeled spanning forest problem: instance analysis and effective heuristic solution

We consider the problem of selecting a fixed number of labels from an edge-labeled, undirected graph such as to minimize the number of connected components in the graph over the edges of the selected labels. We contribute some theoretical considerations, an analysis of instances from the literature, and propose a new heuristic solution procedure for this problem combining a form of GRASP with a cyclic best-first search (CBFS). In computational experiments, we derive some optimal solutions for instances from the literature and compare to exact and heuristic solution procedures from the literature. The experiments suggest that the combination of GRASP and CBFS performs favorably compared to existing solution approaches.