Defesa de: Tese de Doutorado
Candidato(a): Marcos Felipe Medeiros de Souza.
Será defendida no dia 13 de novembro de 2026, às 14h, por videoconferência, a Tese de Doutorado intitulada “Jogos Imparciais em Grafos: Resolvendo o Jogo Kayles Via Programação Dinâmica e Propriedades Periódicas”, do candidato ao título de Doutor em Computação: Marcos Felipe Medeiros de Souza.
Jogos Imparciais em Grafos: Resolvendo o Jogo Kayles Via Programação Dinâmica e Propriedades Periódicas
Resumo:
Nesta tese, consideramos jogos combinatórios nos quais dois jogadores escolhem alternadamente vértices de um grafo finito até que uma condição de vitória seja alcançada. Especificamente, focamos nossa investigação no conhecido jogo Kayles, no qual os vértices selecionados devem formar um conjunto independente, e o jogador que faz a última jogada válida vence (isto é, o jogador que escolhe um vértice que completa um conjunto independente maximal). O Teorema de Zermelo garante que, neste cenário, um dos jogadores possui uma estratégia vencedora – ou seja, uma sequência de jogadas que assegura a vitória independentemente das escolhas do oponente. Dado um grafo, o problema de decisão típico associado a esse tipo de jogo consiste em determinar qual jogador possui uma estratégia vencedora. Responder a essa pergunta significa resolver o jogo
Data: 13 de novembro de 2026, às 14h
Local: Por videoconferência
Link para a defesa: https://meet.google.com/epy-myna-ntc
Resumo
Nesta tese, consideramos jogos combinatórios nos quais dois jogadores escolhem alternadamente vértices de um grafo finito até que uma condição de vitória seja alcançada. Especificamente, focamos nossa investigação no conhecido jogo Kayles, no qual os vértices selecionados devem formar um conjunto independente, e o jogador que faz a última jogada válida vence (isto é, o jogador que escolhe um vértice que completa um conjunto independente maximal). O Teorema de Zermelo garante que, neste cenário, um dos jogadores possui uma estratégia vencedora – ou seja, uma sequência de jogadas que assegura a vitória independentemente das escolhas do oponente. Dado um grafo, o problema de decisão típico associado a esse tipo de jogo consiste em determinar qual jogador possui uma estratégia vencedora. Responder a essa pergunta significa resolver o jogo.
Primeiramente, consideramos o Kayles jogado em caterpillars. Como os caterpillars são grafos de intervalo, já é conhecido um algoritmo de tempo O(n^3) para resolver Kayles nessa classe de grafos. No entanto, investigamos cenários nos quais essa complexidade de tempo pode ser reduzida para O(1) ao estender a propriedade de periodicidade apresentada por Guignard e Sopena (2009) para caterpillars. Provamos que o nimber (nímero) de qualquer caterpillar é igual ao nímero de um caterpillar reduzido equivalente, obtido pela remoção apropriada de certas folhas do grafo original. Ao particionar esses caterpillars reduzidos em classes, mostramos que um período de 34 surge em cada classe investigada, permitindo que o cálculo dos nímeros se estenda para grafos com um grande número de vértices. Apresentamos uma condição suficiente para que uma classe de caterpillars exiba periodicidade 34, usando-a para identificar muitas classes periódicas e calcular o nímero de seus caterpillars em tempo O(1).
Introduzimos também a noção de caterpillars regulares, que generalizam caminhos, e determinamos a sequência nimérica no jogo Kayles de algumas classes de caterpillars regulares. Surpreendentemente, as periodicidades encontradas diferem bastante da periodicidade 34 encontrada para caminhos.
Além disso, apresentamos um algoritmo de programação dinâmica de tempo O(n^2) para resolver Kayles em potências de caminhos, melhorando a complexidade anterior da literatura de O(n^{4}) para grafos com número asteroidal no máximo 2. Por fim, mostramos como esse mesmo algoritmo de tempo O(n^2) pode ser adaptado para resolver o Kayles em potências de ciclos, reduzindo assim a complexidade O(n^3) da literatura para grafos de arcos circulares.
Abstract
In this thesis, we consider combinatorial games in which two players alternately choose vertices from a finite graph until a winning condition is achieved. Specifically, we focus our investigation on the well-known game Kayles, in which the selected vertices must form an independent set, and the player who makes the last valid move wins (i.e., the player who chooses a vertex that completes a maximal independent set). Zermelo’s Theorem guarantees that, in this scenario, one of the players has a winning strategy—that is, a sequence of moves that ensures a win regardless of the opponent’s choices. Given a graph, the typical decision problem associated with this type of game consists of determining which player has a winning strategy. Answering this question means {\em solving the game}.
We first consider Kayles played on caterpillars. Since caterpillars are interval graphs, an O(n^3)-time algorithm for solving Kayles on this graph class is already known. However, we investigate scenarios in which this time complexity can be reduced to O(1) by extending the periodicity property presented by Guignard and Sopena (2009) to caterpillars. We prove that the nimber of any caterpillar is equal to the nimber of an equivalent reduced caterpillar, obtained by appropriately removing certain leaves from the original graph. By partitioning these reduced caterpillars into classes, we show that a period of 34 emerges in each investigated class, allowing the computation of nimbers to scale to graphs with a large number of vertices. We present a sufficient condition for a class of caterpillars to exhibit periodicity 34, using it to identify many periodic classes and to calculate the nimber of their caterpillars in O(1) time.
We also introduce the notion of regular caterpillars, which generalize paths, and determine the nim-sequence for the game of Kayles for certain classes of regular caterpillars. Surprisingly, the periodicities found differ significantly from the periodicity of 34 observed for paths.
Furthermore, we present an O(n^2)-time dynamic programming algorithm for solving Kayles on powers of paths, improving upon the previous O(n^{4})-time complexity in te literature for graphs with an asteroidal number of at most 2. Finally, we show how this same O(n^2)-time algorithm can be adapted to solve Kayles on powers of cycles, thereby reducing the previous O(n^3)-time complexity in the literature for circular-arc graphs.
Banca Examinadora
- Prof. Fábio Protti, UFF – Presidente
- Prof. Luis Antonio Brasil Kowada, UFF
- Prof. Igor Machado Coelho, UFF
- Prof. Átila Arueira Jones, IF Sudeste de Minas
- Prof. Rodolfo Alves de Oliveira, UFF
- Profa. Celina Miraglia Herrera de Figueiredo, UFRJ
Leitura Recomendada em Metodologia de Pesquisa
Para quem está iniciando ou revisando os fundamentos metodológicos de uma pesquisa em Ciência da Computação, seguem algumas referências clássicas e amplamente utilizadas em Mestrados e Doutorados da área:
- Wazlawick, R. S. (2017). Metodologia de Pesquisa para Ciência da Computação. Editora Campus/Elsevier.
- Creswell, J. W., & Creswell, J. D. (2018). Research Design: Qualitative, Quantitative, and Mixed Methods Approaches. SAGE Publications.
- Yin, R. K. (2018). Case Study Research and Applications: Design and Methods. SAGE Publications.
- Wohlin, C., Runeson, P., Höst, M., Ohlsson, M. C., Regnell, B., & Wesslén, A. (2012). Experimentation in Software Engineering. Springer.
- Basili, V. R., Caldiera, G., & Rombach, H. D. (1994). The Goal Question Metric Approach. Encyclopedia of Software Engineering, Wiley.
- Glass, R. L., Ramesh, V., & Vessey, I. (2004). An Analysis of Research in Computing Disciplines. Communications of the ACM, 47(6).
- Shaw, M. (2003). Writing Good Software Engineering Research Papers. Proceedings of the 25th International Conference on Software Engineering (ICSE).
- Easterbrook, S., Singer, J., Storey, M.-A., & Damian, D. (2008). Selecting Empirical Methods for Software Engineering Research. In Guide to Advanced Empirical Software Engineering, Springer.
- Kitchenham, B., & Charters, S. (2007). Guidelines for Performing Systematic Literature Reviews in Software Engineering. EBSE Technical Report.
- Booth, W. C., Colomb, G. G., & Williams, J. M. (2016). The Craft of Research. University of Chicago Press.
Publicado por Maiquel Gomes — maiquelgomes.com.br
Graduado em Ciências Atuariais pela Universidade Federal Fluminense (UFF), Pós-Graduado em Inteligência Artificial, Pós-Graduado em Marketing Digital, Mestrando em IA no Instituto de Computação da UFF (nota máxima no CAPES). Palestrante e Professor de Inteligência Artificial e Linguagem de Programação; autor de livros, artigos e aplicativos.
Professor do Grupo de Trabalho em Inteligência Artificial da UFF (GT-IA/UFF), do Laboratório de Inovação, Tecnologia e Sustentabilidade (LITS/UFF), da Pós-Graduação na Universidade Estácio de Sá, entre outras iniciativas.
Conheça outros projetos:
💫 Apaixonado pela vida, pelas amizades, pelas viagens, pelos sorrisos, pela praia, pelas baladas, pela natureza, pelo jazz e pela tecnologia.
