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

Considere um grafo G em que cv(τ) ∈ {0, 1} denota o estado do vértice v ∈ V (G) em um dado tempo τ ∈ N. Se cv(τ ) = 0, dizemos que o vértice v está inativo ou não-infectado no tempo τ ; caso contrário, dizemos que v está ativo ou infectado no tempo τ . Uma coleção de estados Cτ = (cv (τ ))v∈V (G) é dita uma configuração de G no tempo τ . Uma sequência de configurações P = (Cτ )τ ∈N de G é chamada de um processo dinâmico discreto em G. Dados um grafo G, uma função t : V (G) → N que atribui a cada vértice v de G um valor chamado de limiar de v, e um conjunto S ⊆ V (G) de vértices inicialmente infectados, dizemos que P = It (G, S) é um processo t-irreversível em G se P é um processo dinâmico discreto em G tal que, para todo v ∈ V (G), temos que cv (0) = 1 se e somente se v ∈ S e cv (τ + 1) = 1 se e somente se |{w ∈ NG (v) | cw (τ ) = 1}| ≥ t(v). Ou seja, em um processo t-irreversível P = It (G, S), iniciamos com todos os vértices de S infectados no tempo τ = 0 e, a cada passo de tempo sucessivo, um vértice não-infectado v torna-se infectado se tiver pelo menos seu limiar t(v) de vizinhos infectados no passo de tempo anterior. Além disso, uma vez que um vértice é infectado, ele permanece infectado. Dizemos que o processo termina quando mais nenhum vértice pode ser infectado. Processos irreversíveis são utilizados para modelar diversos fenômenos, entre eles: difusão de (des-)informações e doenças contagiosas. Processos t-irreversíveis são bastante estudados na literatura principalmente com o objetivo de encontrar um conjunto de vértices inicialmente infectados que satisfaça algum critério. Este critério geralmente é maximizar o número de vértices infectados; ou minimizar o tempo necessário para infectar todos os vértices; entre outros similares. Em contextos de contágio e difusão como os citados acima, porém, torna-se natural pensar em como conter a infecção, ou seja, restringir o número de vértices infectados no fim do processo a um conjunto pequeno. Fazemos isto através do que chamamos de imunização de vértices. Um vértice imunizado não pode ser infectado e não contribui para infectar outros vértices. (CORDASCO et al., 2023) introduziu o problema INFLUENCE IMMUNIZATION BOUNDING (IIB) em que, dado um processo t-irreversível P = It (G, S) e naturais k e l, o objetivo é encontrar um conjunto Y ⊆ V (G) de vértices a serem imunizados tal que |Y | ≤ l e o número de vértices infectados ao fim do processo é no máximo k. Dizemos que Y é um conjunto k-restritor. No mesmo artigo, os autores mostraram que o problema é W[1]-difícil e W[2]-difícil parametrizado por alguns parâmetros, entre eles k, l, a largura em árvore do grafo e a diversidade de vizinhança dografo. Eles também mostraram alguns algoritmos FPT parametrizados por combinações destes parâmetros. Neste trabalho, nós estudamos IIB em diversas classes de grafos. Para grafos bipartidos e split, nós mostramos que o problema continua W[2]-difícil parametrizado por l. Mostramos também que IIB é NP-completo mesmo em grafos planares bipartidos subcúbicos. Para árvores, conjecturamos que o problema também permanece NP-completo. Para grafos completos em que os limiares de todos os vértices são iguais, mostramos como encontrar um conjunto k-restritor mínimo. Mostramos também alguns limitantes superiores para o tamanho de um conjunto k-restritor de caminhos, árvores, grafos planares e exoplanares e outras classes de grafos quando k é suficientemente grande e o subgrafo induzido por S é conexo.

• 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)
• Prof. Dr. Nicolas de Almeida Martins (UNILAB)