O problema da floresta geradora k-rotulada

Abstract

In this work, we study the k-Labeled Spanning Forest Problem. Among the problems in edge labeled graphs, this one aims at finding a spanning subgraph that is a forest with the least amount of components and with a positive integer limiting factor k for the number of different labels used. The problem is NP-Hard, as it is a generalization of the Minimal Labeled Spanning Tree Problem, and most of the methods proposed in the literature are based on metaheuristics. We study the characteristics of the problem and relate it to the relevant literature in labeled graphs. Through the studied properties, we establish a class on which the problem is solved in polynomial time. We also explore the characterizations of the problem to propose three mathematical models in 0-1 integer and mixed-integer programming. We propose Branch&Cut methods to solve the problem exactly, using an algorithm to separate Colorful Cuts. Moreover, we propose a parallelization for the only exact method available in the literature, which applies a backtracking procedure. We present preliminary computational experiments with the models and the backtracking method, using test instances suggested by the literature. We apply improvements to the resolution methods by exploring valid inequalities as cuts, branching rules, pruning, and bounds. Besides, we apply Benders decomposition to the proposed flow model. Then, we test the models on graphs with different edge density parameters, still pertinent to the problem. Among these tests, we show the best-found configurations for the models and Cplex.