Problemas de otimização sobre partição em grafos

Resumo

Este é um projeto de pesquisa para doutorado de Phablo Fernando Soares Moura, a ser desenvolvido sob a orientação de Y. Wakabayashi, no Instituto de Matemática e Estatística da USP. Ele se insere na área de otimização combinatória, e tem como foco problemas de partição em grafos com certas restrições. Um dos problemas que serão investigados neste projeto é o problema da recoloração convexa de grafos. Em linhas gerais, neste problema a entrada é um grafo cujos vértices estão coloridos (arbitrariamente), e o objetivo é trocar a cor de um número mínimo de vértices de modo a obter uma coloração tal que, para cada cor, o grafo induzido pelos vértices com essa cor é conexo. Basicamente, a recoloração objetiva definir uma partição do conjunto dos vértices do grafo, tal que cada classe da partição induz um subgrafo conexo de uma das possíveis cores.Este problema tem suas raízes no estudo de árvores filogenéticas, mas estende-se facilmente para versões mais gerais e em grafos arbitrários, tendo sido objeto de estudo sob diversas abordagens. Trata-se de um problema NP-difícil já no caso especial de caminhos. Propomos investigar versões mais gerais desse problema em grafos arbitrários, tendo como foco o estudo de formulações distintas, a relação entre tais formulações e aspectos algorítmicos.