A Complexidade do Problema de Limitação de Influência por Imunização em Grafos Split e Bipartidos - Morais, Samuel S.; Maia, Ana Karolinna; Lima, Carlos Vinícius G. C. (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.9072, 2025)
Dado um grafo G = (V,E), uma função de limiares t : V (G) → N, um conjunto de vértices inicialmente infectados S ⊆ V (G) e naturais k e ℓ, o problema (k, ℓ)-LIMITAÇÃO DE INFLUÊNCIA POR IMUNIZAÇÃO ((k, ℓ)-LII) consiste em encontrar um conjunto de vértices Y ⊆ V (G) a serem imunizados tal que |Y | ≤ ℓ e a imunização de Y restringe a infecção a no máximo k vértices. Este é um problema W[1]-difícil parametrizado por k ou ℓ e W[2]-difícil parametrizado por |S| + ℓ para grafos bipartidos. Neste trabalho, nós mostramos que (k, ℓ)-LII é W[2]-difícil parametrizado por ℓ mesmo em grafos split ou bipartidos com k = |S| e t(v) = dG(v) para todo vértice v ∈ V (G). Nós também mostramos que o problema pode ser resolvido em tempo polinomial em grafos gerais se k = |S| e t(v) = 1 para todo v ∈ V (G) \ S.