O problema da k-Floresta Geradora Balanceada em Arestas

Abstract

The Edge Balanced Spanning k-Forest (k-EBSF) problem consists in, given an undirected edge-weighted graph G and an integer k, finding a spanning forest of G with k trees, in order to minimize the weight of the heaviest tree. In the particular case k = 1, the problem comes down to determining a Minimum Spanning Tree. The problem was introduced in 2017 motivated by applications in computational topology. The k-EBSF has already been shown to be NP-Hard even for k = 2 or for the unit weight case. In this work, we present and prove bounds for the problem and a Dynamic Programming algorithm for the case where the input graph is a path. We introduce two new heuristics for the problem. Furthermore, we propose three Mixed Integer Linear Programming (MILP) formulations for the k-EBSF together with valid inequalities and a variable fixing procedure that aim to strengthen the models. We generated a set of instances to evaluate the quality of the proposed procedures and formulations. Computational tests suggest that the proposed heuristics can be adopted as good upper bounds for the problem. In addition, the formulations F_REP+ and F_ROT+ stood out, managing to find an optimal solution within the time limit in 69.05% and 73.87%, respectively, of the evaluated instances.