Nesta semana, os professores do Departamento de Ciência da Computação (DCC) da UFMG, Guilherme de C. M. Gomes e Vinicius F. dos Santos, foram premiados com o segundo melhor trabalho durante o VIII Encontro de Teoria da Computação. O evento é voltado para a grande área de Teoria da Computação, composto por membros da Comissão Especial em Algoritmos, Combinatória e Otimização (CE-ACO), e tem por objetivo promover uma maior divulgação da área para a comunidade brasileira de computação e afins, por meio do principal evento da Sociedade Brasileira de Computação (SBC), o Congresso da Sociedade Brasileira de Computação (CSBC).
Com o título “Complexidade parametrizada do problema de reconfiguração de separadores”, os autores mostram resultados positivos para uma parametrização estrutural. “Separadores em grafos são conjuntos de vértices cuja remoção destrói todos os caminhos entre dois vértices dados. Em particular, dizemos que um conjunto é um st-separador se sua remoção destrói todos os caminhos entre dois vértices s e t. Problemas de reconfiguração recebem como entrada dois objetos combinatórios e o objetivo é transformar um no outro, mantendo certas propriedades ao longo da transformação. No problema de reconfiguração de separadores, são dados um grafo G e dois st-separadores A e B e deseja-se transformar A em B utilizando certas operações de modificação, de maneira que todos os passos intermediários sejam, também, st-separadores. Este problema é NP-difícil e, em algumas versões, é PSPACE-difícil. Neste trabalho, consideramos pela primeira vez a complexidade parametrizada deste problema de reconfiguração e mostramos resultados positivos para uma parametrização estrutural, além de discutir outras parametrizações naturais”, explicam.
