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 2 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-APXcomplete 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.
1 Introduction 1.1 Let t : V ! N = f1; 2; : : :g be a function assigning integer thresholds to the nodes of G. An assignment of incentives to the nodes of a network G = (V; E) is a cost function c : V ! N0 = f0; 1; 2; : : :g, where c(v) is the incentive given to v 2 V . The effect of applying the 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 in V 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). We assume, w.l.o.g., that3 0 c(v) t(v) d(v).
(otherwise, we can set t(u)=d(u)+1 for every node u with threshold exceeding its degree plus one without changing the problem
{ t(v) if v 2 D c(v) =
maxft(v) dD(v); 0g if v 2 V D:
We say that D is a Threshold-Bounded (TB) dominating set with incentives of cost ∑v2V c(v). We are interested in finding the TB dominating set of minimum cost. Formally, we study the following problem.
THRESHOLD-BOUNDED DOMINATING SET WITH INCENTIVES (TBDI).
Instance: A network G = (V; E) with thresholds t : V ! N.
Problem: Find a set D V of nodes which minimizes the following value. c(D) = ∑ t(v) + ∑ (t(v) dD(v)): (1) v2D t(vv)2>VdDD(v) In the following we will refer to the set D V that minimizes (1) as an optimal TB dominating set in G.4 1.2
Related work Domination in Graphs. Domination problems in graphs have been extensively studied under various assumptions, both from structural and algorithmic points of view. We list here some of them which are close to the one considered in this paper. We assume the graph be G = (V; E).
-domination. Close related to our work is the concept of -domination introduced in
[
is dominated r times, that is, jNM (v)j r. The goal is to minimize the size of M .
Monopolies have been widely studied in the literature, see [
The problem of identifying influential individuals in a social network received a lot
of attention, as it has applications in several areas, including viral marketing, disease
prevention, disease propagation, politics, etc., see [
In this paper, we use the well-known threshold model to study the influence
diffusion process in social networks: For each node v 2 V , the threshold value t(v)
quantifies how hard/easy it is to influence v [
The classical model, also adopted in [
The proposed TBDI problem, in which the cost of totally influence a node is
proportional to the node threshold (that can in turn be proportional to the node influence
capability) and a partial external influence can be applied to each node, can then be used,
among the other possible applications, to model a recommendation system (cfr. [
The TBDI problem considered in this paper coincides with the case in which only one round of influence can be assumed. Indeed our problem can be seen as to find c : V ! N0 of minimum cost ∑v2V c(v) such that D = I0 and I1 = V . In such a case, we can get novel and stronger results as described in Section 1.3.
Our main contributions are the following: In Section 2, we prove that a natural greedy strategy has approximation factor ln ∆ + 2. Unless P N P , the approximation ratio of the greedy algorithm is optimal (up to lower order terms), since the TBDI problem is not easier than the dominating set problem and, consequently, cannot be approximated to within a ratio better than (1 o(1)) ln ∆, unless N P DT IM E(npolylog(n)). In Section 3, we give exact linear-time algorithms for complete and tree networks. 2
General Graphs We show in this section that the TBDI problem can be optimally approximated within a logarithmic factor.
We first notice that the TBDI problem defined in Section 1.1 includes the
dominating set (DS) problem (in case each node has threshold 1). It was shown in [
Theorem 1. The TBDI problem cannot be approximated to within a ratio better than (1 o(1)) ln ∆, unless N P DT IM E(npolylog(n)).
We show now that the logarithmic factor approximation for the TBDI problem can be attained by a greedy algorithm.
In the following, let D V be a TB dominating set, we name black the nodes that belong to the set D. Moreover, for each node v 2 V D we denote by t′(v) = maxft(v) dD(v); 0g (2) the residual threshold of the node v, that is the amount of incentive that still is required to dominate v using D as TB dominating set. Accordingly, we partition the non-black nodes in V D into two sets: Algorithm 1: Greedy-TBDI(G)
Input: A graph G = (V; E) with thresholds t : V ! N.
Result: A TB dominating set D V of minimum cost c(D): 1 D = ∅, W = V 2 forall the v 2 V do t′(v) = t(v) 3 while 9u 2 V D such that t(u) < w(u) do 4 v = argmaxu2V D ( wt((uu)) ) // Select v with largest w(v)=t(v). the set W of white nodes, which contains non-dominated nodes (t′(v) > 0); the set of gray nodes, which contains dominated nodes (t′(v) = 0).
Finally, we denote by w(v) the span of the node v, which corresponds to the number of white neighbours plus the residual threshold (w(v) = dW (v) + t′(v)).
Algorithm 1 greedily selects the node with the largest value w(v)=t(v) until there is a node having threshold smaller that its span. It is possible to see that the algorithm can be implemented in such a way to run in O(jEj log jV j) time. Indeed we need to process the nodes v 2 V according to the metric w(v)=t(v), and the updates that follow each processed node v 2 V involve at most the d(v) neighbors of v.
Theorem 2. Algorithm 1 is a (ln ∆ + 2)-approximation for the TBDI problem.
We first show that the TBDI problem is a special case of the following WTVD problem5:
WEIGHTED TARGETED VECTOR DOMINATION (WTVD).
Input: A graph G = (V; E), thresholds t : V ! N, and a target set U V . Question: Find a set D V of minimum cost ∑v2D t(v) such that dD(u) t(u), for each node u 2 U D.
It is possible to see the existence of a reduction from TBDI to WTVD as follows. Let G = (V; E) with thresholds t : V ! N be an instance of the TBDI problem. For each node v having threshold t(v), we add to the network a set fv1; v2; : : : ; vt(v)g of t(v) nodes having threshold 1, connected to the node v and we obtain an new graph H = (V (H); E(H)) with thresholds tH : V (H) ! N (see Fig. 1) where: - V (H) = U [ U ′, where U = V and U ′ = ∪v2V fv1; v2; : : : ; vt(v)g; - E(H) = E [ E′, where E′ = ∪v2V f(v; vi); for i = 1; 2; : : : ; t(v)g; - tH (v) = { t(v) v 2 U ;
1 otherwise: 5 To the best of our knowledge, this is a novel domination problem which can be of interest on its own. 6
exists a set DH V (H) in H such that ∑v2DH tH (v) each u 2 U DH .
k and dDH (u) k iff there tH (u), for
Algorithm 2 provides a solution DH for the WTVD problem having the same cost of the solution for the TBDI problem. Indeed, the solution for the TBDI problem can be obtained as D = DH \ V . It is worth observing that, since the nodes in V U are set as gray at the beginning of the Algorithm 2 (see line 3), both Algorithms 1 and 2 select the same nodes from the set V = U as long as there exists a node u 2 V D such that t(u) < w(u) (each node v 2 U ′ has t(v) = 1 and w(v) 1). Then Algorithm 1 ends with the set D, while Algorithm 2 continues selecting some nodes in U ′ in order to dominate all the white nodes. As observed above, the cost of the nodes selected in the set U ′ corresponds to the incentives applied to v for the TBDI problem.
Table 1 shows an example of the execution of the Algorithms 1 and 2 on the graph G and H in Fig. 1. For each iteration the set D (TB dominating set), the set W (white nodes) and for each node u, the metric w(u)=t(u) are provided. The Algorithm 1 ends after 2 iterations while the Algorithm 2 needs 3 iterations. We are now going to show that the cost of the solution DH provided by Algorithm 2 is a (ln ∆ + 2)-approximation compared to the cost of an optimal solution D that is
∑∑vv22DDH tt((vv)) ln ∆ + 2: (3)
Each time, the Algorithm 2 selects a new node v of the dominating set (each greedy step), we have cost t(v). Instead of letting this node pay the whole cost, we distribute step D
DH 1 ∅ 2 fv1g 3 –
∅ fv1g fv1; v4g fv2g W w(u)=t(u) v D[fvg DH [fvg
V = U U ′ v1 v2 v3 v4 v5 v6 . . . fv1; v2; v3; v4; v5g 5=2 7=3 5=2 5=2 5=2 1 . . . v1 fv1g fv1g fv2; v3; v4; v5g – 5=3 3=2 5=2 3=2 1 . . . v4 fv1; v4g fv1; v4g – 1=3 1=2 – 1=2 1 . . . v6 – fv1; v4; v6g the cost to all the nodes affected by this choice, plus the node v itself (when t′(v) > 0) according to the portion of the span w(v) covered by each node. For instance consider the node v1 in Fig. 1 having initial threshold t(v1) = 2 : - Assume that v1, is selected in line 5 of the Algorithm 2 when its residual threshold is t′(v1) = 2 (i.e., as a white node) and it has three white neighbors. In this case, the span of the node v1 is w(v1) = dW (v1) + t′(v1) = 5 and each of its white neighbors gets charged t(v1)=w(v1) = 2=5, while v1 is charged (t(v1) t′(v1))=w(v1) = 4=5.
Overall the charge is (t(v1) dW (v1))=w(v1) + (t(v1) t′(v1))=w(v1) = 2 = t(v1): - On the other hand, if v1 is selected as a gray node (t′(v1) = 0), while it has two white neighbors, only the neighbors get charged (they all get t(v1)=w(v1) = 2=2 = 1) and again the overall charge is t(v1).
Assume now that we know a dominating set D of minimum cost ∑ By the definition of the WTVD, each node v, which is not in U D neighbor from D . Hence we can associate to each node v 2 U Then for each node v the nodes in U
D having a dominator (v
we build a star, centered in v , which contains as leaves, that have been associated to it. Hence we have jD j stars, each
presented in Fig. 2. Notice that each node v 2 U have t(v) copies of the node v). Clearly, the contribution of the star centered in v to D appears in t(v) stars (that is we
v 2D t(v ).
has at least t(v) D , t(v) nodes in D . the overall cost of an optimal solution is t(v ).
It is possible to show that the amortized cost (distributed costs) of the Algorithm 2
is at most t(v )(ln ∆ + 2) for each star. This suffices to prove (3).
⊔⊓
3 Efficient algorithms for the TBDI problem
In this section we show that the TBDI problem can be efficiently solved when the graph
G is a complete graph or a tree. Our results improve on those in [
Let Kn = (V; E) be the complete graph with node set V = fv1; v2; : : : ; vng. We will prove the following theorem.
Theorem 3. For any complete network Kn = (V; E), threshold function t : V ! N, the TBDI problem can be solved in linear time.
The following lemma, proved in [
In the following, we assume t(v1) t(v2) : : : t(vn). Notice that the sorting can be done in O(n) time using counting sort because 1 t(v) n 1 = d(v) for all v 2 V .
If the TB dominating set of Kn has j nodes, for some 1 j n, then they are v1; v2; : : : ; vj by Lemma 1; furthermore, each of the n j remaining nodes in V has j neighbors (i.e., v1; v2; : : : ; vj ) in the TB dominating set. For such a remaining node v either t(v) j or v has incentive c(v) = t(v) j. Hence, if we denote by Dj = fv1; v2; : : : ; vj g, it follows that the optimal TB dominating set of Kn is D = arg min c(Dj ) = arg min @∑ t(vi) + 1 j n 1 j n 0 j i=1 n ∑ maxft(vi) i=j+1
1
j; 0gA :
(4)
We show now that D can be computed in time O(n). To this aim, we can pre-compute
an auxiliary vector s where, for j = 1; : : : ; n, s[j] contains the smallest index i j
such that t(vi) > j if it exists, otherwise s[j] = n+1. Clearly, s[
1); and for j = 2; : : : ; n c(Dj ) = n ∑ (t(vi)
j)
j
∑ t(vi) +
i=1
j
= ∑ t(vi) +
i=1
n
∑ (t(vi)
i=s[
Let T = (V; E) be a tree having n nodes. In the following, we will assume that T is rooted at some node r and for any node v, we denote by Tv the subtree rooted at v, by C(v) the set of children of v and, whenever v is not the root r, by p(v) the parent of v. Furthermore, for any incentive function c and any node v, we will denote by c(Tv) the sum of the incentives c assigns to the nodes in Tv.
We give a dynamic programming algorithm that proves Theorem 4.
Theorem 4. For any tree T = (V; E), threshold function t : V problem can be solved in linear time. ! N, the TBDI The algorithm performs a post-order visit of T — so that each node is considered after all of its children have been processed — and for each node v, it solves three different TBDI problems on the subtree Tv, according to some conditions on v regarding the fact that it and its parent belong or not in the TB dominating set.
Definition 1. Let D be a TB dominating set in T . For each v 2 V , we define: Y [v] as the minimum cost for TB dominating all the nodes in Tv, in case v 2 D.
N [v] as the minimum cost for TB dominating all the nodes in Tv, assuming that both v ̸2 D and p(v) 2= D.
R[v], if v ̸= r, as the minimum cost for TB dominating all the nodes in Tv, assuming that v ̸2 D and p(v) 2 D.
of the neighbors of v in D.
We set the above values equal to infinity when their constraints are not satisfiable. For instance for a leaf node v if v 2= D and p(v) 2= D then v can not be dominated and consequently N [v] = 1.
The minimum cost of the TB dominating set in T can then be obtained by computing minfY [r]; N [r]g: (5) We proceed in a post-order fashion, so that the computations of the values Y [v], N [v] and R[v] for a node v are done after all of the values for v’s children are known.
Consider a leaf v (with threshold t(v) = 1) and the one-node subtree Tv. Either v is in the TB dominating set or its parent p(v) is in the dominating set (i.e., the threshold of v in Tv is t(v) 1 = 0), we have that for each leaf node v holds
Y [v] = t(v) = 1 N [v] = 1 R[v] = t(v) 1 = 0 (6) Let v be any internal node. In order to compute the value Y [v], consider that we assume that v is in the TB dominating set and then the incentive of v is exactly its threshold t(v); furthermore, the minimum cost for TB dominating all the nodes in the subtree rooted at any children u 2 C(v) is the minimum between Y [u] (that reflects the case that u belong to the TB dominating set), and R[u] (that reflects the fact that u is not in the TB dominating set while v (the parent of u) is in the TB dominating set and then the threshold of u is t(u) 1). It follows that Y [v]can be computed in O(d(v)) time as ∑
Y [v] = t(v) + minfY [u]; R[u]g:
(7) u2C(v)
Now, we derive the value N [v]. Recalling that in this case v and its parent are not in the TB dominating set we have that its threshold is t(v) and the threshold of each children u 2 C(v) is t(u). In this case at least one of its children should be in the TB dominating set. Let S be a subset of j 1 children of v that are in the TB dominating set. Hence, t(v) j is the incentive of v. Furthermore, the minimum cost for TB dominating all the nodes in each subtree Tu with u 2 S is Y [u], while the minimum cost for TB dominating all the nodes in each subtree Tu with u 2 C(u) S is N [u]. It follows that
0 N [v] = 1 j t(v) S C(v) @t(v) min min jSj=j j + ∑ Y [u] + u2S
∑ u2C(v) S
1 minfY [u]; N [u]gA (8)
The value R(v) can be derived following the same arguments used to have N [v] excepting for the fact that the threshold of v is t(v) 1 and so the parent of v is a neighbor of v in the TB dominating set. This implies that if S is a subset of j children of v that are in the TB dominating set, it holds 0 j t(v) 1. It follows that 0 1 R[v]= 0 jmti(nv) 1 SmCin(v) @t(v) 1 j+ jSj=j ∑ Y [u]+ u2S
∑ u2C(v) S minfY [u]; N [u]gA (9) Example 2. Let T = (V; E) be the three in Fig 3. Using the above strategy, one can easily fill the table in the figure. The minimum cost of the TB dominating set in T corresponds to N [v6] = 4. Indeed an optimal TB dominating set is D = fv4; v5g.
The time complexity of the computation of N [v] and R[v] can be strongly reduced by using a particular ordering of the children of v. Assume to have sorted the d = d(v) 1 children of v, let say v1; v2; : : : ; vd, according to the non-decreasing order of the differences between Y [vi] and N [vi] for each i = 1; ; d, i.e., 1 j +
j t(v) ∑ Y [vi] + ∑ minfY [vi]; N [vi]gA i=1 i=j+1 1 2∆ and then the sorting (10) can be done using counting sort in O(∆) time. To have (11), we make two simple considerations: – Take the incentives assigned to the nodes in Tvi to have N [vi] and increase the incentive assigned to vi so that it becomes t(vi). This gives a new solution for TB dominating all the nodes in Tvi with vi in the TB dominating set; hence, we have Y [vi] t(vi) + N [vi] and so Y [vi] N [vi] t(vi) d(vi) ∆. – On the other hand, take the incentives assigned to the nodes in Tvi to have Y [vi] and, decrease by 1 the incentive assigned to vi, increase the incentive assigned to some u 2 C(vi) so that it becomes t(u) d(u) ∆, and finally increase by 1 the incentive assigned to each of the remaining d(vi) 1 children of vi. This gives a new solution for TB dominating all the nodes in Tvi in which vi is not in the TB dominating set and whose cost is at most Y [vi] 1+d(vi) 1+∆ Y [vi]+2∆ and so Y [vi]+2∆ N [vi]. Lemma 2. If there exists an optimal dominating set D in Tv such that v ̸2 D and j 1 children of v are in D then there exists an optimal dominating set D′ in Tv such that v ̸2 D′ and v1; v2; ; vj 2 D′.
By using the ordering (10) and Lemma 2, the recurrence (8) can be simplified as follows. j +
j t(v) ∑ Y [vi] + ∑ minfY [vi]; N [vi]gA
1 i=1 i=j+1 Hence, (8) can be computed in time O(t). Similarly, (11) can be computed in time O(t).
In conclusion, the value in (5) can be computed in time ∑ O(t(v))
∑ O(d(v)) = O(n): v2V
v2V
Standard backtracking techniques can be used to compute an optimal TB dominating set in the same O(n) time.