Threshold-bounded dominating set with incentives

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.