Complexidade parametrizada do problema de reconfiguração de separadores - Gomes, Guilherme de C. M.; Santos, Vinicius F. dos (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2023.230681, 2023)
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-dificil e, em algumas versões, é PSPACE-dificil. 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.