Processos Reversı́veis em Grafos Densos

Um processo reversível sobre um grafo~$G=(V,E)$ é um processo iterativo tal que, dados uma função de limiar $f:V(G) \rightarrow \mathrm{N}$ e uma rotulação inicial~$c_0 : V(G) \rightarrow \{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 \in \mathrm{N}$. 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. Mostramos um algoritmo polinomial para grafos completos e qualquer~$f$ e estendemos sua solução a grafos blocos e limiares restritos. Provamos também a NP-dificuldade para~\emph{$(k, \ell)$-grafos}, mesmo para~$\max\{k,\ell\} \leq 2$ e~$f(v)=2$, para todo~$v$. Esta prova de NP-completude mostra que o problema dual associado, ou seja, o problema de decidir se~$r_f(G) \leq n-k$, quando parametrizado por~$k$, é W[1]-difícil.