Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Título: Restricting Infections on Graphs: Immunization Problems

Data: 07/03/2025
Horário: 10h
Local: Sala de Seminários – Bloco 952

Resumo:

Dado um grafo G = (V, E), uma função de limiares t : V (G) → N e um conjunto S ⊆ V (G), no modelo de limiar cada vértice de G possui um estado: ativo (ou infectado) e inativo (ou suscetível). Iniciando com todos os vértices de S infectados, um processo de difusão ocorre em passos discretos de forma que um vértice não-infectado torna-se infectado se e somente se ele possui pelo menos t(v) vizinhos infectados. Neste contexto de contágio, é natural questionar sobre como conter a infecção a um conjunto pequeno de vértices do grafo. Podemos fazer isto imunizando alguns vértices. Um vértice imune não é infectado e não influencia na infecção de outros. Neste sentido, Cordasco et al. (2023) introduziu o problema INFLUENCE IMMUNIZATION BOUNDING (IIB) que, dado um grafo G = (V, E) com função de limiar t, um conjunto de vértices inicialmente infectados S ⊆ V (G) e naturais k e l, questiona se é possível obter um conjunto de vértices Y ⊆ V (G) a serem imunizados tal que |Y | ≤ l e, ao  imunizar os vértices de Y , a infecção em (G,t) é restrita a no máximo k vértices. Cordasco et al. (2023) fez um extenso estudo do IIB pelo ponto de vista da complexidade parametrizada, mostrando resultados de W[1]-dificuldade e W[2]-dificuldade com relação a diversos parâmetros como k, l, |S|, a largura em árvore tw(G) e a diversidade de vizinhança nd(G) do grafo. Por outro lado, eles mostraram que IIB é FPT parametrizado por algumas combinações destes parâmetros. Neste trabalho, nós estudamos o IIB em diversas classes de grafos, mostrando um algoritmo polinomial para árvores; valores exatos de Im(G,t, k) para caminhos e grafos completos com limiares iguais; a W[1]-dificuldade do problema parametrizado por k mesmo para grafos cordais; e a NP-completude mesmo para grafos bipartidos, grafos split e grafos planares bipartidos subcúbicos.

Banca examinadora:

• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC) – Orientadora
• Prof. Dr. Carlos Vinícius Gomes Costa Lima (UFCA) – Coorientador
• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC)