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

Detalhes bibliográficos
Ano de defesa: 2022
Autor(a) principal: Pinheiro, Tiago Furtado Drehmer
Orientador(a): Ravelo, Santiago Valdes
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Palavras-chave em Inglês:
Link de acesso: http://hdl.handle.net/10183/238852
Resumo: 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.