Título: Resultados em jogos de coloração e perseguição e grafos bem cobertos

Horário: 09:00h

Data: 17/02/2020

Local: Sala de Seminários - Bloco 952

Resumo:

Nesta tese estudamos três jogos em grafos e o problema da boa cobertura. Para o Jogo da Coloração respondemos uma questão aberta de longa data proposta por Bodlaender em 1991: o número cromático de jogo é PSPACE-difícil. Também mostramos que o número guloso de jogo é PSPACE-difícil. 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. Apesar 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 mostramos um resultado positivo: se o número de guardas é fixo, o Jogo do Espião é solucio- nável em tempo polinomial O(n^{3k+2}) para toda velocidade s ≥ 1 e distância d ≥ 0. Em outras palavras, o Jogo do Espião está em XP quando o parâmetro é o número de guardas. 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 s ≥ 1 e d ≥ 0. Para o problema da boa cobertura, obtemos algoritmos O∗(2^{vc}) e O∗(1.4656^{vc+}) para decidir o problema da boa cobertura de um grafo, melhorando, deste modo, os resultados de Boria et. al. de 2015. Além disso, utilizando a decomposição em coroa, mostramos que os problemas admitem núcleos tendo um número linear de vértices. Em 2018, Alves et. al. provaram que reconhecer grafos bem cobertos é coW[2]-difícil quando α(G) = n − vc(G) é o parâmetro. Contrastando com tal coW[2]-diculdade, apresentamos um algoritmo FPT para decidir a boa cobertura quando α(G) e a degeneração do grafo de entrada G são parâmetros agre- gados. Finalmente, usamos a técnica de decomposição primeval para obter um algoritmo linear para grafos P4-laden estendido e (q, q − 4)-grafos, em que q é o parâmetro, melhorando resultados de Klein et. al. de 2013.

Banca:

• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)
• Prof. Dr. Nicolas de Almeida Martins (UNILAB)
• Prof. Dr. Thiago Braga Marcilon (UFCA)
• Dr. Carlos Vinícius Gomes Costa Lima (MDCC/UFC)