Algoritmos e Complexidade de Problemas de Infecção de Grafos

Um processo reversível sobre um grafo G=(V,E) é um processo iterativo tal que, dados uma função de limiar f:V(G) → N e uma rotulação inicial c₀ : V(G) → {0,1}, cada vértice v muda seu rótulo se e somente se ele possui ao menos f(v) vizinhos com o rótulo oposto, a cada passo de tempo t pertencente aos naturais. Estudamos o problema de determinar o número mínimo r_f(G) de vértices com rótulo inicial 1, tal que todos os vértices alcançam o rótulo 1 definitivamente, em um número finito de passos de tempo. Estudamos a complexidade computacional de determinar r_f(G) para algumas classes de grafos.