Eliminar Ciclos pela Remoção de um Emparelhamento Parametrizado pela Largura em Árvore é FPT - Lima, Carlos V. G. C.; Marcilon, Thiago; Morais, Cícero S. (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
Dado um grafo G = (V,E), um emparelhamento deciclante M ⊆ E(G) de G é um emparelhamento cuja remoção elimina todos os ciclos de G (i.e. G − M é uma floresta). Estudamos o problema de determinar se G admite um emparelhamento deciclante. Já é conhecido que este problema é NPcompleto mesmo para grafos subcúbicos. Neste trabalho mostramos que ele está em FPT quando parametrizado pela largura em árvore.