A line graph reformulation for the rainbow spanning forest problem

Abstract

Seja G(V, E) um grafo conexo e não direcionado, composto pelo conjunto de vértices V e de arestas E, e seja L = {L1, L2, ..., Lh} um conjunto finito de cores. A cada aresta e ∈ E é associada uma cor l ∈ L. Uma floresta geradora F(V, EF ) ⊂ G é dita iridescente se cada componente conexa em F é composta por arestas de cores diferentes. O problema da Floresta Geradora Iridescente consiste então em encontrar uma floresta geradora iridescente para G com o mínimo número de componentes conexas. Neste trabalho, propomos uma formulação de Programação Inteira baseada em grafos linha para o problema, além de desigualdades válidas com o propósito de gerar limites duais mais fortes. Implementamos então um algoritmo Branch-and-cut para resolver a formulação proposta. Experimentos mostram que a formulação proposta apresenta limites duais significativamente melhores que as formulações encontradas na literatura.