Título: Resultados em Jogos de Coloração e Perseguição em Grafos

Data: 02/09/2022

Horário: 14h00

Local: Sala de Seminários - Bloco 952

Resumo:

Nesta tese, estudamos três jogos em grafos. Para o Jogo da Coloração, respondemos a uma questão aberta de longa data proposta por Bodlaender em 1991: o número cromático de jogo é PSPACE-difícil. Mostramos também que o número guloso de jogo é PSPACE-difícil, no Jogo da Coloração Gulosa. De fato, mostramos que ambos os problemas, do Jogo da Coloração e do Jogo da Coloração Gulosa, são PSPACE-Completos, mesmo se o número de cores é o número cromático. Além disso, provamos que o número guloso de jogo é igual ao número cromático para várias superclasses de cografos, estendendo o resultado de Havet e Zhu de 2013. Para o Jogo do Espião, obtemos um limite superior estrito para o produto forte de dois grafos gerais e mostramos exemplos de grafos grades Rei que chegam nesse limite e outros grafos grades Rei que o número de guarda é menor que esse limite. Obtemos também o valor exato do número de guarda no produto lexicográfico de dois grafos gerais para cada distância d>1. Do ponto de vista algorítmico, mostramos o  resultado positivo: se o número k de guardas é fixo, o Jogo do Espião é solucionável em tempo polinomial O(n^{3k+2}) para cada velocidade s>1 e distância d. Em outras palavras, o Jogo do Espião está em XP quando o parâmetro é o número de guardas. Usando o algoritmo XP, obtemos um algoritmo FPT para grafos com poucos P4’s. Como resultado negativo, provamos que o Jogo do Espião é W[2]-difícil mesmo em grafos bipartidos quando o parâmetro é o número de guardas, para cada velocidade s>1 e distância d, estendendo o resultado de Cohen et al. de 2018.

Banca examinadora:

• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
• Profa. Dra. Ana Karolinna Maia de Oliveira (UFC)
• Prof. Dr. Carlos Vinicius Gomes Costa Lima (UFCA)
• Prof. Dr. Nicolas de Almeida Martins (UNILAB)
• Prof. Dr. Thiago Braga Marcilon (UFCA)