Lights Out em grafos: apagando luzes da menor maneira - Couto, Fernanda; Brito, Ighor Bruno de; Sento Sé, Willian de Assis (Anais do Encontro de Teoria da Computação (ETC), 2022)
Lights Out é um quebra-cabeça eletrônico cujo objetivo é encontrar um conjunto de botões que, quando pressionados, apaguem todas as luzes do tabuleiro. Neste trabalho, consideramos a generalização cuja entrada é um grafo e focamos na versão de minimização, onde o objetivo é determinar o número mínimo de vértices que devem ser acionados para apagar todo o grafo. Trabalhamos com grafos Caterpillar, Snarks Flor e Snarks Goldberg. Para auxiliar na obtenção dos resultados, implementamos um software que simula o jogo para qualquer grafo de entrada e também um algoritmo força-bruta que soluciona a versão de minimização.