NP-Completeness, Approximation Results and Mixed Integer Linear Programming Methods for the Minimum Labeling Spanning k-Forest Problem

An edge-labeled graph (ELG) is a graph such that each edge has a label associated. Given an ELG G, the minimum labeling spanning k-forest problem consists in finding a spanning forest F of G with minimum number of labels and number of components bounded by k. In this work, a complexity study is realized and an approximation algorithm for the problem is proposed. Continuing on a previous study of a mathematical programming model, we propose two valid inequalities
to reinforce it and analyze computational experiments.