The k-labeled Spanning Forest Problem

AbstractIn the k-labeled Spanning Forest Problem (kLSF), given a graph G with a label (color) assigned to each edge, and an integer positive value kmax we look for the minimum number of connected components that can be obtained by using at most kmax different labels. The problem is strictly related to the Minimum Labelling Spanning Tree Problem (MLST), since a spanning tree of the graph (i.e. a single connected component) would obviously be an optimal solution for the kLSF, if it can be obtained without violating the bound on kmax. In this work we present heuristic and exact approaches to solve this new problem