The k-labeled spanning forest problem : complexity, approximability, formulations and algorithms

Abstract

In this work, we study the k-labeled spanning forest problem (KLSF). The input of the KLSF is an undirected graph with labeled edges and a positive integer k. The goal is to find a spanning forest of the graph with at most k different labels associated with the edges, that minimizes the number of components. KLSF finds practical applications in different scenarios related to networks design and telecommunications. Its solutions may help to reduce the negative impact of electromagnetic fields exposure on the population health or to increase profits of internet management companies, among others. The in terest in the KLSF problem is not only practical but also theoretical since the problem generalizes the best-known NP-hard minimum labeling spanning tree problem (MLST). This work reinforces the NP-hardness of the KLSF and ensures that, even for the simple instances where the components of the original graph are only triangles and edges, the problem is NP-hard. Also as a theoretical result, an inapproximability proof is presented for it, ensuring that unless P = NP there is no polynomial time algorithm with approxi mation factor polynomial in the number of the labels. To complete the theoretical results a trivial 3-approximation result is presented for the particular case where the input graph components are edges or triangles. From the application side, to approach KLSF, we propose a fix-and-optimize matheuristic that was tested over several instances, achieving high-quality solutions in reasonable computational time. When compared to the best known algorithms in the literature, our matheuristic outperformed the other proposals in most cases, finding better solutions in less computational time for the most challenging instances.