A Complexidade do Problema de Limitação de Influência por Imunização em Grafos Split e Bipartidos

• Samuel S. Morais UFC
• Ana Karolinna Maia UFC
• Carlos Vinícius G. C. Lima UFCA

DOI: https://doi.org/10.5753/etc.2025.9072

Resumo

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.

Referências

Banerjee, A. V. (1992). A simple model of herd behavior. The quarterly journal of economics, 107(3):797–817.

Barabási, A.-L. e Pósfai, M. (2016). Network science. Cambridge University Press, Cambridge.

Bondy, J. A. e Murty, U. S. R. (2008). Graph Theory. Springer, New York.

Chen, N. (2009). On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, 23(3):1400–1415.

Cordasco, G., Gargano, L., e Rescigno, A. A. (2023). Immunization in the threshold model: A parameterized complexity study. Algorithmica, 85(11):3376–3405.

Downey, R. G. e Fellows, M. R. (2012). Parameterized complexity. Springer Science & Business Media.

Dreyer, P. A. e Roberts, F. S. (2009). Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Applied Mathematics, 157(7):1615–1627.

Finbow, S. e MacGillivray, G. (2009). The firefighter problem: a survey of results, directions and questions. Australas. J Comb., 43:57–78.

Granovetter, M. (1978). Threshold models of collective behavior. American journal of sociology, 83(6):1420–1443.

Hartnell, B. (1995). Firefighter! an application of domination. In the 24th Manitoba Conference on Combinatorial Mathematics and Computing, University of Minitoba, Winnipeg, Cadada, 1995.

Kempe, D., Kleinberg, J., e Tardos, E. (2003). Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, page 137–146, New York, NY, USA. Association for Computing Machinery.

Mello, I. F., Squillante, L., Gomes, G. O., Seridonio, A. C., e de Souza, M. (2021). Epidemics, the ising-model and percolation theory: a comprehensive review focused on covid-19. Physica A: Statistical Mechanics and its Applications, 573:125963.

Morris, S. (2000). Contagion. The Review of Economic Studies, 67(1):57–78.

Newman, M. E. J. (2010). Networks: an introduction. Oxford University Press, Oxford; New York.

Wang, W. e Street, W. N. (2018). Modeling and maximizing influence diffusion in social networks for viral marketing. Applied network science, 3:1–26.