Motivated by some problems in the area of influence spread in social networks, we introduce a new variation on the domination problem which we call Threshold-Bounded Domination with Incentives. Let G = (V, E) be a graph with an influence threshold t(v) for each node. An assignment of external incentives to the nodes of G is a cost function c : V → N0, where c(v) is the incentive given to v ∈ V . The effect of applying incentive c(v) to node v is to decrease its threshold, i.e., to make v more susceptible to be dominated. A node is in the Threshold-Bounded dominating set D if it receives an incentive equal to its threshold, that is, c(v) = t(v). A node, which is not in D, is dominated if the number of its neighbors in D plus the incentives it has received is at least equal to the node threshold t(v). The goal is to minimize the total of the incentives required to ensure that all the nodes are dominated. The problem is log-APX-complete in general networks with unbounded degree. We prove that a greedy strategy has approximation factor ln ∆ + 2, where ∆ is the maximum degree of a node. We also give exact linear time algorithms for some classes of graphs.

Threshold-bounded dominating set with incentives

Cordasco, Gennaro;Gargano, Luisa;Rescigno, Adele A.
2018-01-01

Abstract

Motivated by some problems in the area of influence spread in social networks, we introduce a new variation on the domination problem which we call Threshold-Bounded Domination with Incentives. Let G = (V, E) be a graph with an influence threshold t(v) for each node. An assignment of external incentives to the nodes of G is a cost function c : V → N0, where c(v) is the incentive given to v ∈ V . The effect of applying incentive c(v) to node v is to decrease its threshold, i.e., to make v more susceptible to be dominated. A node is in the Threshold-Bounded dominating set D if it receives an incentive equal to its threshold, that is, c(v) = t(v). A node, which is not in D, is dominated if the number of its neighbors in D plus the incentives it has received is at least equal to the node threshold t(v). The goal is to minimize the total of the incentives required to ensure that all the nodes are dominated. The problem is log-APX-complete in general networks with unbounded degree. We prove that a greedy strategy has approximation factor ln ∆ + 2, where ∆ is the maximum degree of a node. We also give exact linear time algorithms for some classes of graphs.
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: https://hdl.handle.net/11386/4719651
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact