We consider the problem of controlling the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node’s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and ℓ, is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most ℓ nodes? We consider several parameters associated with the input, including the bounds k and ℓ, the maximum node degree Δ, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.

Parameterized Complexity of Immunization in the Threshold Model

Cordasco G.;
2022

Abstract

We consider the problem of controlling the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node’s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and ℓ, is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most ℓ nodes? We consider several parameters associated with the input, including the bounds k and ℓ, the maximum node degree Δ, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.
978-3-030-96730-7
978-3-030-96731-4
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11591/468814
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact