A pre-processing heuristic for the k-labeled spanning forest problem

Given a positive integer k and a graph in which each edge has an associated label, the k-labeled spanning forest problem (kLSFP) is an NP-Hard combinatorial optimization problem that consists in finding a spanning forest of the graph with minimum number of connected components by using at most k labels. The problem was originally defined to model an application related to telecommunications networks and generalizes another better known problem called the minimum labeling spanning tree problem (MLSTP). In this paper, we propose a new pre-processing heuristic that breaks cycles of the input graph. We performed computational experiments and a statistical analysis to evaluate the effectiveness of the pre-processing heuristic used within a branch-and-cut method.