Latency-Bounded Target Set Selection in Signed Networks

Abstract

It is well-documented that social networks play a considerable role in information spreading. The dynamic processes governing the diffusion of information have been studied in many fields, including epidemiology, sociology, economics, and computer science. A widely studied problem in the area of viral marketing is the target set selection: in order to market a new product, hoping it will be adopted by a large fraction of individuals in the network, which set of individuals should we “target” (for instance, by offering them free samples of the product)? In this paper, we introduce a diffusion model in which some of the neighbors of a node have a negative influence on that node, namely, they induce the node to reject the feature that is supposed to be spread. We study the target set selection problem within this model, first proving a strong inapproximability result holding also when the diffusion process is required to reach all the nodes in a couple of rounds. Then, we consider a set of restrictions under which the problem is approximable to some extent.

1. Introduction

The study of diffusion processes is a widely investigated topic in the complex networks setting. It aims at analyzing how local interactions among nearby nodes may lead to the diffusion, possibly over the whole network, of some feature (opinion/information/disease) starting from a limited set of initiator (or seed) nodes. The problem known as Influence Maximization has been introduced by Domingos and Richardson [1,2] for the design of viral marketing campaigns on social networks by using a small (let us say, given) number of initiators (for example by providing a limited set of people free samples of a product to be merchandised), starting from which a cascade is triggered maximizing the overall spreading of information (see also [3,4,5,6,7,8,9]). Dually, the target set selection problem aims at finding out a minimum size set of initiators able to spread the feature over the whole network [3,10,11,12,13,14,15,16,17] or over a large (let us say, given) portion of the network; such a set of initiators is called a target set.

Diffusion processes are usually modeled by graphs in which each vertex may be in one out of two states: informed or unaware. Initially, only nodes in a given set $I_0$ are informed, while all the others are unaware; while the diffusion process goes on, nodes may change their states according to the diffusion rule of the process. A diffusion rule may be reversible, if changes from informed to unaware are allowed, or irreversible if a node can no longer change its state once it becomes informed. In a discrete diffusion model, nodes (eventually) change their state at discrete time steps. In the rest of this paper, we shall only deal with discrete irreversible diffusion processes.

Several rules to govern the transition from unaware to informed have been proposed, and many papers have studied the dynamics of these systems mostly in stochastic scenarios (see [18,19] and references quoted therein). In the Independent Cascade Model [6,20] an edge-weighted graph is assumed and, as soon as a node u becomes informed, each currently unaware neighbor v of u changes its state to informed with probability equal to the ratio between the weight of arc $(u,v)$ and the sum of weights of all arcs incident on u. A deterministic counterpart of this model is that of a Majority Process [21,22,23] in which, at each time step, a vertex changes its state if and only if at least half of its neighbors are in the opposite state.

The Linear Threshold Model [5,6,24,25,26] is based on the association of a threshold $\theta \left(v\right)$ to each node v and of a weight $w(u,v)$ to each arc $(u,v)$: node u becomes informed if and only if ${\sum }_{v\in N\left(u\right)\cap I}w(u,v)\ge \theta \left(u\right)$, where $N\left(u\right)$ is the set of neighbors of u and I is the set of the already informed nodes. In other words, the Linear Threshold Model assumes that any unaware node becomes informed if the weight of its informed neighbors is above a certain threshold (i.e., the node is subject to a large enough amount of “social pressure”). In [25,27] a special case of the Linear Threshold Model is considered, in which all arc weights are 1 and all nodes have the same threshold $\theta$; in this case, the threshold value just stands for the number of neighbors that have to be informed in order to induce a node to become informed. In that paper, the authors prove that deciding if a graph has a target set of size d is an NP-complete problem for $\theta \ge 3$. Chen [13] then strengthened such result by showing the NP-hardness of the problem even for $\theta =2$ and proved that, in the same hypothesis, no polynomial-time algorithm exists with approximation factor better than $O\left(2{log}^{1-ϵ}\right|V\left|\right)$ also when all nodes have constant degrees, unless $\mathrm{NP}\subseteq DTIME\left(n^{polylogn}\right)$; in the same paper a polynomial-time algorithm to find an optimal solution has been provided when the underlying graph is a tree. Other interesting cases in which the problems become tractable are studied in [16]. In [3], Ben-Zwi et al. proved that the problem can be solved in time $O\left(M^w\right|V\left|\right)$ where M is the maximum threshold value and w is the treewidth of the graph: since M cannot exceed the maximum node degree, this proves that the problem is fixed-parameter tractable if parametrized with respect to both treewidth and the maximum node degree of the graph.

The aforementioned papers did not consider the issue of the number of time steps necessary for the feature diffusion. However, this is a relevant point in many settings: in viral marketing, for instance, it is quite important to spread information quickly. Indeed, research in Behavioural Economics shows that humans make decisions mostly on the basis of very recent events [28,29]; furthermore, marketing strategies are more effective when the time needed to reach all the target individuals is short. Hence, it is a worthwhile goal to study diffusion processes while taking into account the number of time steps within which it is required to have all the nodes informed and, actually, this topic has already received some attention. Indeed, as pointed out by the authors, the inapproximability result proved in [13] for general graphs still holds when the diffusion process is required to end in a bounded number of time steps (16 time steps, in fact). In [24] a polynomial-time algorithm spreading a feature over a set of required size within a constant number of time steps in graphs of bounded clique-width has been proposed. Following [24], in this paper, diffusion processes with an available fixed number of time steps within which informing all the nodes will be called latency-bounded diffusion processes.

All diffusion rules considered so far assume that nodes are always positively influenced by their neighbors, that is, any node always has increased its support in favor of the feature being spread throughout the network whenever one of its neighbors becomes informed. However, in most network settings also negative link effects are to be considered.

One way to take into account negative feedbacks is that pursued in [30,31,32,33] where it is assumed that individuals may also develop a negative opinion about the feature to be spread and, in this case, they may negatively influence their neighbors. In [30] a generalization of the Independent Cascade model is proposed in which each initiator turns positive (experiencing good quality of the feature) with probability q and turns negative (disliking the feature) with probability $1-q$, and then, at each time step, a node having become positively informed in the previous step tries to inform each of its unaware neighbors: if successful (with success probability p) the neighbor becomes positively informed with probability q and negatively informed with probability $1-q$; meanwhile, a negatively informed node in the previous step tries to negatively inform its unaware neighbors, and if successful the neighbors become negatively informed. In [33], instead, a generalization of the Linear Threshold model is proposed in which each node (which can be inactive, positively active or negatively active) v has a belief score $r\left(v\right)$ (measuring the amount of trust that the node places on its own judgment) and a threshold $\theta \left(v\right)$, and each arc has a weight $w(u,v)$; a node is activated the first time the sum of weights from its active neighbors plus its own belief score exceeds its threshold and, after being activated, the node decides on its attitude (positive or negative) based on the ratio between the positive influence (sum of weights from positively activated friends) and negative influence (sum of weights from negatively activated friends).

A different approach to negative feedbacks is tackled in [34,35] taking into account the possibility that some relations between individuals are ruled by, for instance, antagonism and distrusting (see [36] and references quoted therein). Actually, in all papers cited so far, it is assumed that nodes always trust their neighbors and, hence, they get support in favor to accept the feature by their neighbors having a positive opinion about it and they get support in favor to discard the feature by their neighbors having a negative opinion about it. Conversely, it is now assumed that node opinions about the feature to be spread are always positive but that receiving positive feedback from an untrusted/antagonist neighbor results in increasing the support to discard the feature. Ahmed et al. [34] presented a new threshold model to incorporate positive and negative influences among individuals in which the effect of negative influence is the tendency of individuals in not adopting a product adopted by their opponent: each arc $(u,v)$ has a weight $p(u,v)\in [0,1]$, each node v has a couple of threshold values, ${\theta }^{+}\left(v\right)$ and ${\theta }^{-}\left(v\right)$ and, at any time step, if $S^{+}$ and $S^{-}$ are, respectively, the sets of the trusted and untrusted active neighbors of v at that time step, v becomes active if $1-{\Pi }_{u\in S^{+}}(1-p(u,v))>{\theta }^{+}\left(v\right)$ and $1-{\Pi }_{u\in S^{-}}(1-p(u,v))<{\theta }^{-}\left(v\right)$. In [35], echoing the principles that “the friend of my enemy is my enemy” and “the enemy of my enemy is my friend”, a reversible model is presented in which positive relationships carry the influence in a positive manner, i.e., you would more likely trust and adopt your friends’ opinions, while negative relationships often carry influence in a reverse direction (if your foe chooses one opinion or votes for one candidate, you would more likely be influenced to do the opposite): at each step, every node randomly picks one of its neighbors, and if the arc from this neighbor is positive the node adopts the neighbor’s decision (to accept the feature or not), while if the edge is negative the node adopts the opposite of the neighbor’s decision.

In [37,38] the two approaches (positive/negative opinions and positive/negative relationships) are jointly considered. In [37], an extension of the independent cascade model is proposed in which each node u has an opinion $o_u\in [-1,1]$, each link $(u,v)$ has a probability of interaction ${\phi }_{u,v}\in [0,1]$ and a probability of activation $p(u,v)$: as soon as u becomes active, it gets a unique chance of turning v active with probability $p(u,v)$; if v is activated by u, then the probability that v gets informed with the same orientation of u is ${\phi }_{u,v}$, and the probability that v gets informed with the opposite orientation is $1-{\phi }_{u,v}$. In [38] another extension of the independent cascade model is introduced in which nodes may be in one of the three states: positively active, negatively active or inactive; when node v becomes somehow active, it tries to activate each one of its inactive neighbor nodes with its same opinion (positive if it is positively active or negative if it is negatively active) in the case its relation with that neighbor is positive, with opposite opinion in the case its relation with that neighbor is negative.

The interest of most of the cited papers is in the Influence Maximization problem with the goal, in case positive/negative opinions are considered, of maximizing the spread of positive opinions. We also notice that most of the proposed models taking into account negative feedback effects are stochastic.

In this paper we follow the same approach to negative feedback effects as in [34,35], introducing a deterministic diffusion model in which nodes’ opinions about the feature to be spread are always positive but the relationships between nodes may be positive or negative. In more detail, we consider a generalization of the Linear Threshold Model in which the set of neighbors of each node is partitioned into two subsets: one subset of trusty neighbors (or friends), containing the neighbors able to positively influence the node, and one subset of unreliable neighbors (or enemies), containing the neighbors able to negatively influence the node. Informally speaking, in our model an unaware node becomes informed at some time step only if at that time step the cumulative influence coming from its informed trusty neighbors is at least as large as the node threshold, and at that time step as well as at any previous time step the cumulative influence coming from its informed unreliable neighbors is less than the node threshold. Notice that, as in [30], positive and negative influences are slightly asymmetric in that negative feedback effects are more powerful than positive ones in influencing a node: indeed, in [30] a negatively informed node always tries to negatively inform its unaware neighbors (while there is a chance that a node gets negatively informed by a positively informed neighbor), and in our model an unaware node will never become informed if at some time step the cumulative influence from its enemies exceeds the threshold (also if in the same time step the cumulative influence from its friends exceeds the threshold too). In fact, several studies in social psychology (e.g., [39,40,41,42]) point out that negative impact is usually stronger and much more dominant than positive impact in shaping people’s decisions. Notice also that our rule according to which an unaware node becomes informed is quite similar to that in [34], discussed above (although [34] deals with the Influence Maximization problem). The main difference between the two rules is that, while the rule herein defined directly generalizes that in in the Linear Threshold model in its considering the cumulative amount of information reaching an unaware node (i.e., we sum up the weights of informed neighbors), the rule in [34] is somehow related to that in the Independent Cascade model: in fact, in that paper, the function associated to the set $S^{+}$ of the informed friends (and similarly as to the informed enemies) is $1-{\Pi }_{u\in S^{+}}(1-p(u,v))$ which denotes the probability of accepting, let’s say, the suggestion coming from at least one informed friend in the hypothesis of independent probabilities of accepting the suggestion from any of them.

Within this setting, we consider a problem that is closely related to that studied in [24], that is, computing a minimum size set able to spread a feature to all the network nodes within a given number k of time steps. We shall call such a set a k-target set.

2. Results and Discussion

After providing the formal definitions in Section 3, in Section 4 we prove that computing both a minimum size 2-target set and a minimum size target set (of unbounded latency) with respect to our diffusion rule is Min Horn Deletion-complete with respect to a reduction preserving approximability properties of (NPO) optimization problems (we shortly and informally recall that a problem $\mathcal{P}$ is $\mathcal{Q}$-complete with respect to some reduction $\alpha$, for some problem $\mathcal{Q}$, if $\mathcal{P}$ is $\alpha$-reducible to $\mathcal{Q}$ and $\mathcal{P}$ is $\alpha$-reducible to $\mathcal{Q}$. If this happens, for any property $\pi$ preserved by $\alpha$, $\mathcal{P}$ satisfies $\pi$ if and only if $\mathcal{Q}$ satisfies $\pi$. Needless to say, $\mathcal{P}$ is $\mathcal{Q}$-complete if and only is $\mathcal{Q}$ is $\mathcal{P}$-complete). Hence, the two problems are both contained in the class poly-APX and NP-hard to approximate to within $2^{{log}^{1-ϵ}\left|V\right|}$ for any $ϵ>0$, also when node thresholds and arc weights are all equal to 1, that is, when the diffusion rule is a direct generalization of the one in [25].

In Section 5, we start the study of the problem in which a minimum size 1-target set has to be computed. Such a problem is trivially Set Cover-hard also when node thresholds and arc weights are all equal to 1. We start by showing that the same reduction used to upper bound the complexity of the unbounded latency and of the latency 2 cases actually yields a $({\Delta }^{+}+1)$-approximation for the latency 1 diffusion processes, where ${\Delta }^{+}$ is the maximum in-degree in the graph of the positive relations. We notice that the $({\Delta }^{+}+1)$-approximation does not depend in any way on the topology of the graph of the negative relations.

The study of the way the complexity of the search for 1-target sets is related to the topology of the graph of the negative relations is started in Section 5.1: we first show the problem is in PO when restricted to instances such that the graph of the negative relations is a generalized chain (that is, the graph obtained by replacing each of its strongly connected components by a node is a directed chain), then we get a non-polynomial time $(log|V|+1)$-approximation algorithm for general graph by reducing to weighted Set Cover. Finally, we show that such algorithm runs in polynomial time when the graph of the negative relations is a generalized source tree, that is when the graph obtained by replacing its strongly connected components by nodes is a source tree, thus yielding a polynomial-time $(log|V|+1)$-approximation algorithm for generalized source trees. It is worthwhile to remark that the results in Section 5.1 hold whatever topology of the graph of the positive relations is considered.

We observe that the study of diffusion processes of duration 1 is also of some interest in the graph-theoretic setting. In fact, the search for a minimum 1-target set with respect to the Linear Threshold rule can be seen also as the search for some kind of dominating set. As an example, 1-target sets with respect to the diffusion rule in [25], in which an unaware node becomes informed as soon as $\theta$ of its neighbors are informed, are just $\theta$-dominating sets [43]. Similarly, 1-target sets with respect to our unweighted diffusion rule correspond to a sort of dominating sets with constrained pairs: given a graph $G=(V,E)$ and a set C of pairs of nodes, a constrained dominating set is $D\subseteq V$ of nodes such that i) for any $u\in V-D$ there is $v\in V$ such that $(v,u)\in E$ and ii) for any $(u,v)\in C$ either $u\in D$ and $v\in D$ or $u\notin D$ and $v\notin D$.

3. Model and Problems Definitions

A signed graph $G=(V,A^{+}\cup A^{-})$ is the overlapping of two directed graphs, $G^{+}=(V,A^{+})$ and $G^{-}=(V,A^{-})$, over the same set of nodes. For an example of the definitions to follow, refer to Figure 1.

For any $u\in V$, we denote as $N_{in}^{+}\left(u\right)$ and $N_{in}^{-}\left(u\right)$, respectively, the sets of in-friends and of in-enemies of u, that is, the in-neighbors of u in $G^{+}$ and in $G^{-}$:

$$N_{in}^{+}\left(u\right)=\{v\in V:(v,u)\in A^{+}\}\mathrm{and}{N}_{in}^{-}\left(u\right)=\{v\in V:(v,u)\in A^{-}\}.$$

Similarly, for each $u\in V$, we define the sets of out-friends and out-enemies of u as

$$N_{out}^{+}\left(u\right)=\{v\in V:(u,v)\in A^{+}\}\mathrm{and}{N}_{out}^{-}\left(u\right)=\{v\in V:(u,v)\in A^{-}\}.$$

A path in $G^{+}$ between any pair of nodes in V is called a positive path and $D^{+}$ denotes the maximum length of a shortest positive path. For $u\in V$, we denote as ${\pi }^{+}\left(u\right)$ the set of nodes such that, for any $v\in {\pi }^{+}\left(u\right)$, G contains a positive path from v to u and, for $v\in {\pi }^{+}\left(u\right)$, as $d^{+}(v,u)$ the length of a shortest positive path in G from v to u. Finally, for $u\in V$ and $V^{\prime }\subseteq V$,

$$d^{+}(V^{\prime },u)=\left\{\begin{array}{cc}min\{d^{+}(v,u):v\in V^{\prime }\cap {\pi }^{+}\left(u\right)\}\hfill & \mathrm{if}{V}^{\prime }\cup {\pi }^{+}\left(u\right)\ne \varnothing ,\hfill \\ D^{+}+1\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

Negative paths, $D^{-}$, ${\pi }^{-}\left(u\right)$, $d^{-}(u,v)$ and $d^{-}(V^{\prime },u)$ are defined similarly.

Let $\theta :V\to {\mathbb{N}}^{+}$ and $w:A^{+}\cup A^{-}\to {\mathbb{N}}^{+}$ be, respectively, a node-weight and an arc-weight function. A set $I_0\subseteq V$ of initially informed nodes (all the remaining nodes in $V-I_0$ being unaware) may eventually start a $(\theta ,w)$-diffusion process: at time step 1 any node $u\in V-I_0$ becomes informed if the cumulative weight of its in-friends is at least $\theta \left(u\right)$ while the cumulative weight of its in-enemies is less than $\theta \left(u\right)$, that is

$$\sum _{v\in N_{in}^{+}\left(u\right)\cap I_0}w(v,u)\ge \theta \left(u\right)\mathrm{and}\sum _{v\in N_{in}^{-}\left(u\right)\cap I_0}w(v,u)<\theta \left(u\right);$$

We denote as $I_1$ the set of nodes becoming informed at time step 1.

Conversely, if the cumulative weight of u’s in-enemies is at least $\theta \left(u\right)$, then the negative influence that u receives from $N_{in}^{-}\left(u\right)$ will induce it to remain in the unaware state forever, that is, at any successive time step u will never become informed. We say u becomes refractory. Needless to say, if neither the cumulative weight of u’s in-friends nor the cumulative weight of u’s in-enemies reaches $\theta \left(u\right)$, u does not change its state.

Inductively, if $I_j$ denotes the set of nodes becoming informed at time step j, an unaware node $u\in V-{\cup }_{j=0}^{t-1}{I}_j$ becomes refractory at time step $t>1$ if

$$\sum _{v\in N_{in}^{-}\left(u\right)\cap \left(I_0\cup I_1\cup \cdots \cup I_{t-1}\right)}w(v,u)\ge \theta \left(u\right),$$

(1)

while it becomes informed if (1) does not hold and

$$\sum _{v\in N_{in}^{+}\left(u\right)\cap (I_0\cup I_1\cup \cdots \cup I_{t-1})}w(v,u)\ge \theta \left(u\right).$$

A set $I_0\subseteq V$ is a target set for $\langle G=(V,A^{+}\cup A^{-}),\theta ,w\rangle$ if ${\cup }_{t\ge 0}{I}_t=V$. Needless to say, the size of a target set $I_0\subseteq V$ is $|I_0|$.

The Signed Target Set Selection problem (STSS) asks for computing a minimum size target set for a given signed graph $G=(V,A^{+}\cup A^{-})$ with node- and arc-weight functions $\theta$ and w. The Unweighted Signed Target Set Selection problem (USTSS) is the restriction of STSS in which all node- and arc-weights equal 1.

Notice that, if $I_t=\varnothing$ for some $t\ge 0$, then $I_s=\varnothing$ for all $s>t$. The latency of a diffusion process is, therefore, defined as the integer $t\in {\mathbb{N}}^{+}$ such that $I_t\ne \varnothing$ and $I_{t+1}=\varnothing$. The t-TSS (t-USTSS) problem asks for computing minimum size target sets yielding diffusion processes of latency t.

4. Complexity of Approximation of USTSS and 2-USTSS

We shortly recall that an A-reduction (see [44]) is a reduction between a pair of (NPO) optimization problems transforming (in polynomial time) instances of a problem P to instances of a problem Q so that a solution for an instance $x_P$ of P can be recovered in polynomial time from a solution $x_Q$ of the corresponding instance of Q and, for some $\alpha >0$, a r-approximate solution for $x_Q$ is a $\alpha r$-approximate solution for $x_P$. Informally speaking, A-reductions preserve the approximability properties of (NPO) optimization problems. In this section, we shall prove that 2-USTSS and USTSS are both Min Horn Deletion-complete with respect to A-reductions. Such a result will follow by a couple of A-reductions involving the weakly positive-minimum ones problem proved to be Min Horn Deletion-complete with respect to A-reductions in [44].

In more detail, we first A-reduce the weakly positive-minimum ones problem to 2-USTSS in Section 4.1, and this together with the results in [44], and Lemmas 1 and 2, will prove the following theorem.

Theorem 1.

For any $ϵ>0$, 2-USTSS (and, hence, USTSS) is NP-hard to approximate to within $2^{{log}^{1-ϵ}\left|V\right|}$.

Then, in Section 4.2 we A-reduce USTSS to weakly positive-minimum ones in order to get the Min Horn Deletion-completeness of both USTSS and 2-USTSS. In turn, this implies that 2-USTSS and USTSS are in poly-APX.

Let $X=\{x_1,\dots ,x_n\}$ be a set of boolean variables; a set of clauses (i.e., disjunction of literals) $f=\{c_1,\dots ,c_m\}$ on X such that, for each $c_j\in f$, $c_j$ contains at most one negative variable is said weakly positive. If f is a set of weakly positive clauses, a clause in f will be called positive if all literals it contains are positive variables, and it will be called negative if it contains one negated variable.

An instance of weakly positive-minimum ones is a pair $\langle X,f\rangle$, where $X=\{x_1,\dots ,x_n\}$ is a set of boolean variables and $f=\{c_1,\dots ,c_m\}$ is a weakly positive set of clauses; the weakly positive-minimum ones problem asks for computing a minimum size subset of X to be set to $\mathtt{true}$ in order to satisfy all clauses in f.

In what follows, with a slight abuse of notation, we shall sometimes write $x_i\in c_j$ ($\neg x_i\in c_j$) as a shorthand to mean that $x_i$ ($\neg x_i$) is a literal of clause $c_j$ (so that $c_j$ is considered as a set of literals, instead of their disjunction). We shall say that a variable $x_i$ is positively contained in a clause $c_j$ if $x_i\in c_j$, and that $x_i$ is negatively contained in $c_j$ if $\neg x_i\in c_j$.

Let $\langle X,f\rangle$ be an instance of weakly positive-minimum ones; without loss of generality, in what follows we shall always assume that at least one clause in f is positive (otherwise all clauses in f would be satisfied by setting to $\mathtt{true}$ no variable in X) and that each clause in f contains at least a couple of variables (one of which positive). Indeed, if some clause in f consists of a single positive variable then such variable has to be necessarily set to $\mathtt{true}$ in order to satisfy f, and a smaller set of clauses $f^{\prime }$ can be derived by removing from f all clauses containing that variable and an optimum solution for f is obtained by adding the variable to an optimum solution for $f^{\prime }$. Similarly, if some clause in f consists of a single negative variable then such variable has to be necessarily set to $\mathtt{false}$ in order to satisfy f, and a smaller set of clauses $f^{\prime }$ can be derived by removing from f all clauses containing that negative variable and an optimum solution for f is an optimum solution for $f^{\prime }$. Hence, f is satisfied by assigning $\mathtt{true}$ to all the n variables in X, and f is not satisfied by assigning $\mathtt{false}$ to all the n variables in X.

4.1. weakly positive-minimum ones ${\le }_A$ 2-USTSS

We now derive from an instance $\langle X,f\rangle$ of weakly positive-minimum ones a signed network $G=(V,A^{+}\cup A^{-})$ (see Figure 2):

• we set $V=V_X\cup V_{\overline{X}}\cup V_f$, where $V_X=\{u_i:x_i\in X\}$, $V_{\overline{X}}=\{\overline{u_i}:x_i\in X\}$ and $V_f=\{v_j:c_j\in f\}$;
• for each $x_i\in X$, $(u_i,\overline{u_i})$ is an arc in $A^{+}$ and $(\overline{u_i},u_i)$ is an arc in $A^{-}$;
• for each $u_i,u_j\in V_X$, $(u_i,u_j)$ is an arc in $A^{+}$ and $(u_j,u_i)$ is an arc in $A^{+}$ (that is, nodes in $V_X$ form a clique of positive arcs);
• for each clause $c_j$ and for each $x_i$ positively contained in $c_j$, $(u_i,v_j)$ is an arc in $A^{+}$ and $(v_j,u_i)$ is an arc in $A^{-}$;
• if $c_j$ is a negative clause and $\neg x_h$ is its negative variable, then $({\overline{u}}_h,v_j)$ is an arc in $A^{-}$;
• if $c_j\in f$ is a positive clause then, for any $x_i\in X-\{x_k:x_k\in c_j\}$, $({\overline{u}}_i,v_j)$ is an arc in $A^{-}$.

Needless to say, computing G requires polynomial time in $\left|f\right|$.

The next lemma proves that it suffices to search in $V_X$ for a target set for G.

Lemma 1.

For any target set $I\subseteq V$ for G there exists a target set $I_0$ for G such that $|I_0|\le |I|$ and $I_0\subseteq V_X$.

Proof. 

Recall that each clause in f contains at least one positive variable.

Let $I\subseteq V$ be a target set for G. Notice that, since all in-friends of any node in $V_X$ are contained in $V_X$ (that is, $N_{in}^{+}\left(u\right)\subseteq V_X$ for any $u\in V_X$), then nodes in $V_X$ can get informed by nodes in $V_X$ only; consequently, it must be $I\cap V_X\ne \varnothing$.

Suppose there exists $i\in \{1,\dots ,n\}$ such that ${\overline{u}}_i\in I$: since $({\overline{u}}_i,u_i)\in A^{-}$, it must be $u_i\in I$ (or $u_i$ could not be informed, contradicting that I is a target set). On the other hand, since $(u_i,{\overline{u}}_i)\in A^{+}$ and $N_{in}^{-}\left(\overline{u_i}\right)=\varnothing$, $u_i$ is able to inform ${\overline{u}}_i$. Finally, since $N_{out}^{+}\left(\overline{u_i}\right)=\varnothing$, ${\overline{u}}_i$ is unable to inform any node, this proves that $I-\left\{{\overline{u}}_i\right\}$ is still a target set for G. So, $I_1=I-V_{\overline{X}}$ is a target set for G.

Similarly, if there exists $v_j\in V_f\cap I_1$, then, since $(v_j,u_i)\in A^{-}$ for any $x_i\in X$ positively contained in $c_j$, $I_1$ is a target set for G only if $u_i\in I_1$. On the other hand, since $(u_i,v_j)\in A^{+}$, since $N_{in}^{-}\left(v_j\right)\subset V_{\overline{X}}$, and since $I_1\cap V_{\overline{X}}=\varnothing$, then $u_i$ is able to inform $v_j$. Since $N_{out}^{+}\left(v_j\right)=\varnothing$, $v_j$ is unable to inform any other node, and, hence, $I_1-\left\{v_j\right\}$ is still a target set for G, and so is $I_0=I_1-V_f$. □

The next lemma shows that the construction defined in this subsection is actually an A-reduction, so completing the proof that weakly positive-min ones${\le }_A$USTSS.

Lemma 2.

For any $k\in {\mathbb{N}}^{+}$, with $1\le k\le n$, f is satisfiable by assigning $\mathtt{true}$ to k variables in X if and only if there exists a target set for G of size k.

Proof. 

Suppose f is satisfiable by the truth assignment a assigning $\mathtt{true}$ to $k\ge 1$ variables in X. We show that the set $I_0=\{u_i\in V_X:a\left(x_i\right)=\mathtt{true}\}$ is a target set for G.

We start by noticing that all nodes in $V_X-I_0$ become informed at time step 1, and that all nodes in $V_{\overline{X}}$ become informed at time step 1 or 2 so that they cannot negatively influence any node at time step 1. Since a satisfies f, any positive clause $c_j$ contains a (positive) variable $x_i$ such that $a\left(x_i\right)=\mathtt{true}$; hence, $u_i\in I_0$ and $v_j$ becomes informed at time step 1. Hence, all nodes in $V_f$ corresponding to positive clauses become informed at time step 1.

Let $c_j$ be a negative clause and let $u_h$ be its negative variable: a satisfies $c_j$ either by assigning $\mathtt{false}$ to $u_h$ or by assigning $\mathtt{true}$ both to its negative variable and to at least one of its positive variables. In the former case, ${\overline{u}}_h$ becomes informed at time step 2 and, since all nodes corresponding to positive variables in $c_j$ become informed at time step 0 or 1 (whether they are in $I_0$ or not), it cannot forbid $v_j$ to get informed at time step 2. In the latter case, both $v_j$ and $u_h$ become informed at time step 1 so that ${\overline{u}}_h$ cannot forbid $v_j$ to get informed.

Hence, all nodes in G are informed (by time step 2), that is, $I_0$ is a target set for G, and $|I_0|=k$.

Conversely, let $I_0\subseteq V$ be a target set for G. By Lemma 1, we can assume $I_0\subseteq V_X$.

$$a\left(x_i\right)=\left\{\begin{array}{cc}\mathtt{true}\hfill & \mathrm{if}{u}_i\in I_0,\hfill \\ \mathtt{false}\hfill & \mathrm{if}{u}_i\notin I_0.\hfill \end{array}\right.$$

Let $c_j$ be a positive clause in f. If, $u_i\notin I_0$ for any $x_i\in c_j$, then $v_j$ could become informed only at time step 2; since $I_0\subset V_X$, then there exists $u_{\ell }\in I_0-c_j$ so that ${\overline{u}}_{\ell }$ is informed at time step 1 and, since $({\overline{u}}_{\ell },v_j)\in A^{-}$, it would forbid $v_j$ to become informed, contradicting that $I_0$ is a target set. Hence, for any positive clause $c_j$ in f there exists $x_i\in c_j$ such that $a\left(x_i\right)=\mathtt{true}$.

Let $c_j$ be a negative clause in f, let $x_h$ be its negative variable and let $x_{j_1},\dots ,x_{j_q}$ be its positive variables. If $a\left(x_{j_i}\right)=\mathtt{false}$ for any $i=1,\dots ,q$, and, hence, $\{u_{j_1},\dots ,u_{j_q}\}\cap I_0=\varnothing$, then, as already noticed, $v_j$ could become informed only at time step 2. In this case it must be $u_h\notin I_0$: indeed, if $u_h\in I_0$ then ${\overline{u}}_h$ would get informed at time step 1 and, since $({\overline{u}}_h,v_j)\in A^{-}$, this would forbid $v_j$ to become informed, so contradicting that $I_0$ is a target set for G. Hence, if $a\left(x_{j_i}\right)=\mathtt{false}$ for any $1\le i\le q$, then it must be $a\left(x_h\right)=\mathtt{false}$ too.

Summarizing, a satisfies each clause in f, that is, a satisfies f, and a assigns $\mathtt{true}$ to $|I_0|$ variables. □

We finally observe that the latency of any cascade occurring in the signed graph in the reduction here described is at most 2. This proves that, for any $t\ge 2$, t-USTSS is min Horn Deletion-hard.

4.2. USTSS${\le }_A$weakly positive-minimum ones

We now derive from a signed graph $G=(V,A^{+}\cup A^{-})$ a set $f_G$ of weakly positive clauses.

Before proceeding, we need a preliminary lemma.

Lemma 3.

A set $I_0\subseteq V$ is a target set for $G=(V,A^{+}\cup A^{-})$ if and only if for any $u\in V-I_0$

• ${\pi }^{+}\left(u\right)\cap I_0\ne \varnothing$, and
• for any $v\in N_{in}^{-}\left(u\right)$, it holds that $d^{+}(I_0,u)\le d^{+}(I_0,v)$.

Proof. 

We start by noticing that, since node thresholds and arc weights are all equal to 1, the diameter $D^{+}$ of $G^{+}$ upper bounds the latency of any diffusion process in G: indeed, for any $u\in V$, if any of the u’s neighbors is informed at time step t, either u becomes informed at time step $t+1$ or it will never become informed. As a consequence, for any target set $I_0$ and for any $u\in V$, u may become informed at time step $t\le D^{+}$ only if $d^{+}(I_0,u)=t$.

Suppose $I_0\subseteq V$ is a target set for G; hence, $V-I_0$ can be partitioned into at most $D^{+}$ subsets $I_1,\dots ,I_{D^{+}}$ such that all individual-nodes in $I_t$ become informed at time step t, for any $1\le t\le D^{+}$. This implies that, for any $t=1,\dots ,D^{+}$ and for any $u\in I_t$, $d^{+}(I_0,u)=t$ and, hence, ${\pi }^{+}\left(u\right)\cap I_0\ne \varnothing$.

Let $u\in I_t$, for some $t=1,\dots ,D^{+}$: if there exists $v\in N_{in}^{-}\left(u\right)\cap I_s$ for some $s\le t-1$, v would forbid u to get influenced at time step t. Hence, for any $v\in N_{in}^{-}\left(u\right)$, it must hold that $v\in {\cup }_{s\ge t}{I}_s$, that is, $d^{+}(I_0,u)\le d^{+}(I_0,v)$. This proves the first part of the assertion.

Conversely, suppose that, for any $u\in V-I_0$, ${\pi }^{+}\left(u\right)\cap I_0\ne \varnothing$ and, for any $v\in N_{in}^{-}\left(u\right)$, it holds that $d^{+}(I_0,u)\le d^{+}(I_0,v)$. For any $1\le t\le D^{+}$, denote as $V_t$ the set of nodes $u\in V-I_0$ such that $d^{+}(I_0,u)=t$. Since for any node $u\in V_1$, $N_{in}^{-}\left(u\right)\cap I_0=\varnothing$ by hypothesis, all nodes in $V_1$ are influenced at time step 1. Inductively, it can then be proved that, for any $t\le D^{+}$, all nodes in $V_t$, are influenced at time step t. This proves that $I_0$ is a target set for G. □

To model $G=(V,A^{+}\cup A^{-})$ by a weakly positive set of clauses $f_G$, we start by defining the set $X=\{x_u:u\in V\}$ of boolean variables, each of which witnesses whether the corresponding node is initially informed or not. Then, we describe the set of clauses defining $f_G$, which is partitioned into a set P of positive clauses and a set Q of negative clauses: that is, $f_G=P\cup Q$.

Let u be any node and let ${\pi }^{+}\left(u\right)$ be the set $\{v_1,\dots ,v_j\}$. P contains a single clause $c_u$ associated to u which models the requirement that u is initially informed or it can become informed in a further step:

$$c_u=x_u\vee x_{v_1}\vee x_{v_2}\vee \cdots \vee x_{v_j}.$$

Similarly, for any $u\in V$, Q contains a set $Q_u$ of clauses associated to u, modeling the requirement that u is initially informed or it can become informed earlier than any node in $N_{in}^{-}\left(u\right)$. For each $v\in N_{in}^{-}\left(u\right)$, $Q_u$ contains the clause

$$(\neg x_v\vee x_u)$$

(2)

and, for each $1\le t\le D^{+}$ and for each $z\in {\pi }^{+}\left(v\right)$ such that $d^{+}(z,v)=t$, $Q_u$ contains the clause

$$(\neg x_z\vee x_u\vee x_{w_1}\vee x_{w_2}\vee \cdots \vee x_{w_k}),$$

where $\{w_1,w_2,\dots ,w_k\}=\{w\in V:d^{+}(w,u)\le t\}$.

Summarizing, $f_G=P\cup Q$, with $P=\{c_u:u\in V\}$ and $Q={\cup }_{u\in V}{Q}_u$. Needless to say, $f_G$ is computable in polynomial time from G. Furthermore, there is a one-to-one correspondence among subsets of V and truth assignments for X: for any $V^{\prime }\subseteq V$, we denote as $a_{V^{\prime }}$ the truth assignment corresponding to $V^{\prime }$, that is,

$$a_{V^{\prime }}\left(x_u\right)=\left\{\begin{array}{cc}\mathtt{true}\hfill & \mathrm{if} u\in V^{\prime },\hfill \\ \mathtt{false}\hfill & \mathrm{if} u\in V-V^{\prime }.\hfill \end{array}\right.$$

The next lemma proves that the just described construction is actually an A-reduction from USTSS to weakly positive-minimum ones.

Lemma 4.

Let $G=(V,A^{+}\cup A^{-})$ be a signed graph. $I_0\subseteq V$ is a target set for G if and only if the truth assignment $a_{I_0}$ satisfies $f_G$.

Proof. 

Let $I_0\subseteq V$ be a target set for G.

For any $u\in I_0$, since $x_u\in c_u$ and, for any clause $c\in Q_u$, $x_u\in c$, then $a_{I_0}$ satisfies $c_u$ and every clause in $Q_u$.

For any $u\in V-I_0$, since $I_0$ is a target set for G, then, by Lemma 3, ${\pi }^{+}\left(u\right)\cap I_0\ne \varnothing$: let $z_u\in {\pi }^{+}\left(u\right)\cap I_0$ be such that $d^{+}(z_u,u)=min\{d^{+}(w,u):w\in {\pi }^{+}\left(u\right)\cap I_0\}$. By construction, $x_{z_u}\in c_u$, and, hence, $c_u$ is satisfied by $a_{I_0}$. Furthermore, for any $v\in N_{in}^{-}\left(u\right)$, let $y_v\in {\pi }^{+}\left(v\right)\cap I_0$ be such that $d^{+}(y_v,v)=min\{d^{+}(w,v):w\in {\pi }^{+}\left(v\right)\cap I_0\}$: by Lemma 3, for any $v\in N_{in}^{-}\left(u\right)$, $d^{+}(z_u,u)\le d_V(y_v,v)$ and, hence, for any $v\in N_{in}^{-}\left(u\right)$, and for any $w\in {\pi }^{+}\left(v\right)\cap I_0$, $x_{z_u}$ is contained in every clause in $Q_u$ containing $\neg x_w$. As a consequence, every clause $c\in Q_u$ containing $\neg x_w$ as its negative variable such that $a_{I_0}\left(x_w\right)=\mathtt{true}$, also contains $x_{z_u}$; since $z_u\in I_0$, $a\left(x_{z_u}\right)=\mathtt{true}$ and, hence, c is satisfied by $a_{I_0}$. This proves that every clause $c\in Q_u$ containing $\neg x_w$ as its negative variable such that $a\left(x_w\right)=\mathtt{false}$ is satisfied by a.

In conclusion, for any $u\in V$, $a_{I_0}$ satisfies $c_u$ and all clauses in $Q_u$.

Conversely, suppose $a_{I_0}$ satisfies $f_G$. For any $u\in V-I_0$, since $a_{I_0}$ satisfies $c_u$, there must exist at least one node $z\in {\pi }^{+}\left(u\right)$ such that $a\left(x_z\right)=\mathtt{true}$ and, hence, $z\in I_0$. This proves that ${\pi }^{+}\left(u\right)\cap I_0\ne \varnothing$.

Furthermore, for any $u\in V-I_0$ and $v\in N_{in}^{-}\left(u\right)$, and for any $y\in {\pi }^{+}\left(v\right)\cap I_0$ (that is, $a_{I_0}\left(x_y\right)=\mathtt{true}$ and v may become informed by a path from y), any clause in $Q_u$ containing $\neg x_y$ has also to contain a positive variable $x_z$ such that $a_{I_0}\left(x_z\right)=\mathtt{true}$. By construction of the clauses in $Q_u$, this implies that $d^{+}(z,u)\le d^{+}(y,v)$, that is, $d^{+}(I_0,u)\le d^{+}(I_0,v)$.

By Lemma 3, this proves that $I_0$ is a target set for G. □

5. The 1-USTSS Problem

The 1-USTSS problem is trivially Set Cover-hard: actually, a dominating set of a graph $G=(V,E)$ is also a 1-target set for the signed graph $G^{\prime }=(V,A^{+}\cup A^{-})$ where $A^{+}=\{(u,v),(v,u):\{u,v\}\in E\}$ and $A^{-}=\varnothing$. Hence, 1-USTSS is non-approximable within $clog\left|V\right|$ for some $c>0$.

In the remainder of this section, we study the approximability of 1-USTSS.

We start by noticing that if a diffusion process of latency 1 is required to occur, then the A-reduction described in Section 4.2 yields a weakly positive set of clauses such that all its negative clauses have size 2 (that is, they contain exactly one positive literal and one negative literal). In fact, it directly follows from Lemma 3 that $I_0\subseteq V$ is 1-target set for a signed graph $G=(V,A^{+}\cup A^{-})$ if and only if for any $u\in V-I_0$

• $N_{in}^{+}\left(u\right)\cap I_0\ne \varnothing$, and
• for any $v\in N_{in}^{-}\left(u\right)$, it holds that $v\in V-I_0$.

As a consequence, for any $u\in V$ the set of the negative clauses associated to u (as defined in Section 4.2) is

$$Q_u=\{(\neg x_v\vee x_u):v\in N_{in}^{-}\left(u\right)\}.$$

(3)

This proves that the A-reduction shown in Section 4.2 works also as an A-reduction from 1-USTSS to weakly positive minimum ones such that the set of clauses corresponding to a signed graph, besides being weakly positive, has all its negative clauses of size 2. In [44] it is shown that the weakly positive minimum ones problem is B-approximable when restricted to such instances, where B is the maximum size of a positive clause in the set.

The size of the positive clauses in the set $f_G$ described in Section 4.2 is very large: for $u\in V$, $|c_u|=1+|{\pi }^{+}\left(u\right)|$, since $c_u$ had to state that u is in $I_0$ or there exists some node in $I_0$ connected to u by a path (of any length). However, when diffusion processes of latency 1 are to be described, $f_G$ can be slightly modified in order to decrease the size of its positive clauses: more precisely, condition a above implies that, for each $u\in V$, $c_u=x_u\vee x_{v_1}\vee \cdots \vee x_{v_j}$ where $\{v_1,\dots ,v_j\}=N_{in}^{+}\left(u\right)$, that is, $|c_u|=|N_{in}^{+}\left(u\right)|+1$.

Hence, by denoting as ${\Delta }^{+}$ the maximum in-degree of a node in $G^{+}$, that is, ${\Delta }^{+}=max\left\{\right|N_{in}^{+}\left(u\right)|:u\in V\}$, the next theorem follows from Lemma 4, from definition (3) and from the already cited result in [44].

Theorem 2.

The 1-USTSS problem is $({\Delta }^{+}+1)$-approximable, where ${\Delta }^{+}=max\left\{\right|N_{in}^{+}\left(u\right)|:u\in V\}$.

We remark that the result in Theorem 2 only depends on the topology of $G^{+}$, no matter which is the topology of $G^{-}$. Throughout the next subsection we shall follow the opposite way, that is, we shall study the complexity of 1-USTSS in relation to the topology of $G^{-}$, no matter which is the topology of $G^{+}$.

5.1. 1-USTSS and $G^{-}$

Let $G=(V,A^{+}\cup A^{-})$ be a signed graph. Notice that any $I\subseteq V$ is a target set for G only if, for each $u\in I$, it holds that $N_{out}^{-}\left(u\right)\subseteq I$. In turn, if I is a target set for G containing u and, hence, $N_{out}^{-}\left(u\right)$, then I must contain also $N_{out}^{-}\left(v\right)$, for any $v\in N_{out}^{-}\left(u\right)$. More precisely, if we define, for each $u\in V$, the set $\mathcal{E}\left(u\right)$ containing u and all the nodes reachable from u by a path in $G^{-}$, that is,

$$\mathcal{E}\left(u\right)=\left\{u\right\}\cup \{v\in V:u\in {\pi }^{-}\left(v\right)\},$$

then the next fact holds, which follows from the previous observation by a simple inductive argument.

Fact 1: If $I\subseteq V$ is a target set for $G=(V,A^{+}\cup A^{-})$ then, for any $u\in I$, $\mathcal{E}\left(u\right)\subseteq I$.

Observe now that, if $G^{-}$ is strongly connected, then, for any $u\in V$, it holds that $\mathcal{E}\left(u\right)=V$; hence, by Fact 1, we get

Fact 2: If $G^{-}$ is strongly connected, then the only target set for G (no matter about its latency) is V.

For any $E\subseteq V$, we define the set

$$S\left(E\right)=E\cup \{u\in V:d^{+}(E,u)=1\}=E\cup \{u\in V:\exists z\in E\cap N_{in}^{+}\left(u\right)\},$$

that is, the set of nodes that are or may become informed within time step 1 whenever all nodes in E are contained in the set of the initially informed nodes.

Lemma 5.

$I\subseteq V$ is a 1-target set for $G=(V,A^{+}\cup A^{-})$ if and only if $S\left(I\right)=V$ and, for any $u\in I$, $\mathcal{E}\left(u\right)\subseteq I$.

Proof. 

If $I\subseteq V$ is a 1-target set for $G=(V,A^{+}\cup A^{-})$, then, trivially, $S\left(I\right)=V$ and, by Fact 1, for any $u\in I$, $\mathcal{E}\left(u\right)\subseteq I$.

Conversely, suppose that $S\left(I\right)=V$ and, for any $u\in I$, $\mathcal{E}\left(u\right)\subseteq I$. Then, for any node $x\in V-I$,

• since $S\left(I\right)=V$, there exists $y\in I$ such that $(y,x)\in A^{+}$ (that is, y may inform x at time step 1) and, furthermore,
• since for any $u\in I$, $\mathcal{E}\left(u\right)\subseteq I$, then, for any $z\in V$ such that $(z,x)\in A^{-}$, since $x\in {\pi }^{-}\left(z\right)$ and $x\notin I$, $z\notin I$ (that is, any node that could forbid x to become informed is not in I). □

Lemma 5 allows us to prove membership to PO of 1-USTSS when restricted to chain and generalized chain graphs. The chain graph over the node set $V=\{v_1,\cdots ,v_n\}$ is made of the set of arcs $\{(v_j,v_{j-1}):j=2,\cdots ,n\}$. A generalized chain graph consists of a set $C_1,\dots ,C_n$ of strongly connected components linked to each other in a chain-like topology, that is, for any $j=2,\dots ,n-1$ and for any $u\in C_j$, arc $(u,v)$ exists only if $v\in C_{j-1}$.

Theorem 3.

The 1-USTSS problem restricted to instances $G=(V,A^{+}\cup A^{-})$ such that $G^{-}=(V,A^{-})$ is a chain or a generalized chain graph is in PO.

Proof. 

If $G^{-}$ is a chain, that is, $V=\{v_1,\cdots ,v_n\}$ and $A^{-}=\{(v_j,v_{j-1}):j=2,\cdots ,n\}$, then $\mathcal{E}\left(v_1\right)=\left\{v_1\right\}$, $\mathcal{E}\left(v_2\right)=\{v_1,v_2\}=\left\{v_2\right\}\cup \mathcal{E}\left(v_1\right)$ and, in general, for $i\ge 2$, $\mathcal{E}\left(v_i\right)=\left\{v_i\right\}\cup \mathcal{E}\left(v_{i-1}\right)$. Hence, $\mathcal{E}\left(v_1\right)\subseteq \cdots \subseteq \mathcal{E}\left(v_n\right)$.

Correspondingly, $S\left(\mathcal{E}\left(v_1\right)\right)\subseteq \cdots \subseteq S\left(\mathcal{E}\left(v_n\right)\right)$: indeed, for any $i=1,\dots ,n-1$,

$$S\left(\mathcal{E}\left(v_i\right)\right)=\mathcal{E}\left(v_i\right)\cup \{u\in V:\exists z\in \mathcal{E}\left(v_i\right)\cap N_{in}^{+}\left(u\right)\}\subseteq \mathcal{E}\left(v_{i+1}\right)\cup \{u\in V:\exists z\in \mathcal{E}\left(v_{i+1}\right)\cap N_{in}^{+}\left(u\right)\}.$$

As a consequence, by Lemma 5, $\mathcal{E}\left(v_m\right)$ is a minimum size 1-target set for G, where $m=min\{j\in \{1,\dots ,n\}:S\left(\mathcal{E}\left(v_j\right)\right)=V\}$.

Let $G^{-}$ be a generalized chain and let $C_1,\dots ,C_n$ be its strongly connected components. As already stated in the observation leading to Fact 2, for any $j=1,\dots ,n$ and for any $u,v\in C_j$, it holds that $\mathcal{E}\left(u\right)=\mathcal{E}\left(v\right)$: hence, in what follows we shall use the notation ${\mathcal{E}}_j$ to refer to any set $\mathcal{E}\left(u\right)$ for $u\in C_j$.

By the same argument holding for chain graphs, for any $j=1,\dots ,n$, we get that ${\mathcal{E}}_j$ contains all nodes in any $C_i$ with $i\le j$. Hence, again by a similar reasoning to that holding in the chain case, since ${\mathcal{E}}_1\subseteq \cdots \subseteq {\mathcal{E}}_n$, we get that ${\mathcal{E}}_m$ is a minimum size 1-target set for G, where $m=min\{j\in \{1,\dots ,n\}:S\left({\mathcal{E}}_j\right)=V\}$. □

Lemma 5 shows that any 1-target set is actually obtained by choosing a subcollection of sets in the collection $\mathcal{E}=\left\{\mathcal{E}\right(u):u\in V\}$. We now introduce the collection $\overline{\mathcal{E}}$ as the closure of $\mathcal{E}$ under non-empty intersections: that is, $\mathcal{E}\subseteq \overline{\mathcal{E}}$, and, for each $E_1,E_2\in \overline{\mathcal{E}}$ such that $E_1\cap E_2\ne \varnothing$, $E_1\cup E_2\in \overline{\mathcal{E}}$.

The introduction of $\overline{\mathcal{E}}$ allows us to describe any target set for G as the union of pairwise disjoint subsets, that is:

Fact 3: For any target set I for $G=(V,A^{+}\cup A^{-})$, there exists $\mathcal{B}\subseteq \overline{\mathcal{E}}$ such that $I={\cup }_{B\in \mathcal{B}}B$ and, for any $B_1,B_2\in \mathcal{B}$, $B_1\cap B_2=\varnothing$.

Based on fact 3, we now show how to get in over polynomial time a $(1+log|V\left|\right)$-approximate solution for 1-USTSS by a (non-polynomial-time) reduction from 1-USTSS to minimum Weighted Set Cover (WSC) and by the $(1+log|V\left|\right)$-approximation algorithm for WSC [45]. Later in this section, we shall discuss cases in which the procedure overall runs in polynomial time.

Recall that an instance of WSC is a triple $\langle X,\mathcal{S},w\rangle$ where $\mathcal{S}\subseteq 2^X$, ${\cup }_{S\in \mathcal{S}}S=X$, and $w:\mathcal{S}\to {\mathbb{N}}^{+}$; the goal is finding a minimum weight set $\mathcal{C}\subseteq \mathcal{S}$ such that ${\bigcup }_{C\in \mathcal{C}}C=X$, where the weight of $\mathcal{C}$ is defined as $w\left(\mathcal{C}\right)=\sum _{C\in \mathcal{C}}w\left(C\right)$.

Let $G=(V,A^{+}\cup A^{-})$ be a signed graph; the corresponding instance $\langle X_G,{\mathcal{S}}_G,w_G\rangle$ of WSC is obtained by setting $X_G=V$, ${\mathcal{S}}_G=\{S\left(E\right):E\in \overline{\mathcal{E}}\}$ and, for each $E\in \overline{\mathcal{E}}$, $w_G\left(S\left(E\right)\right)=\left|E\right|$.

Lemma 6.

Let $G=(V,A^{+}\cup A^{-})$ be a signed graph and $E_1,\dots ,E_k\in \overline{\mathcal{E}}$; $I_0={\cup }_{j=1}^k{E}_j$, is a 1-target set for G if and only if $\mathcal{C}=\{S\left(E_1\right),\cdots ,S\left(E_k\right)\}$ is a set cover for $X_G$. Furthermore, if $E_1,\dots ,E_k$ are pairwise disjoint then $|I_0|=w_G\left(\mathcal{C}\right)$.

Proof. 

Let $E_1,\dots ,E_k$ be elements of $\overline{\mathcal{E}}$ and let $I_0={\cup }_{j=1}^k{E}_j$. By definition, $I_0$ is a 1-target set for G if and only if $S\left(I_0\right)=V$. Hence,

$$S\left(I_0\right)=\bigcup _{j=1}^{k}S\left(E_j\right)=V=X_G,$$

that is, $\mathcal{C}=\{S\left(E_1\right),\cdots ,S\left(E_k\right)\}$ is a set cover of X.

If $E_1,\dots ,E_k$ are pairwise disjoint, then

$$|I_0|=\left|\bigcup _{j=1}^k{E}_j\right|=\sum _{j=1}^k\left|E_j\right|=\sum _{j=1}^k{w}_G\left(S\left(E_j\right)\right)=w_G\left(\mathcal{C}\right).$$

 □

The previous lemma shows that the proposed transformation is actually a reduction and that, if a 1-target set for G is described as the union of pairwise disjoint elements of $\overline{\mathcal{E}}$, then its size equals the weight of the corresponding set cover of $X_G$.

Notice that, if ${\mathcal{C}}^{*}$ is an optimal solution for the instance $\langle X_G,{\mathcal{S}}_G,w_G\rangle$ of WSC corresponding to G then, for any $S\left(E_1\right),S\left(E_2\right)\in {\mathcal{C}}^{*}$, it holds that $E_1\cap E_2=\varnothing$: indeed, if there exist $S\left(E_1\right),S\left(E_2\right)\in \mathcal{C}$ such that $E_1\cap E_2\ne \varnothing$, since $E_1\cup E_2\in \overline{\mathcal{E}}$ and, thus, $S(E_1\cup E_2)\in {\mathcal{S}}_G$ and, moreover, $S\left(E_1\right)\cup S\left(E_2\right)=S(E_1\cup E_2)$, then the set ${\mathcal{C}}^{\prime }={\mathcal{C}}^{*}-\{S\left(E_1\right),S\left(E_2\right)\}\cup \left\{S(E_1\cup E_2)\right\}$ would still be a set cover for $X_G$ and

$$\begin{array}{ccc}\hfill \sum _{C\in {\mathcal{C}}^{\prime }}{w}_G\left(C\right)& =& \sum _{C\in \mathcal{C}*}{w}_G\left(C\right)-w_G\left(S\left(E_1\right)\right)-w_G\left(S\left(E_2\right)\right)+w_G\left(S(E_1\cup E_2)\right)\hfill \\ & =& \sum _{C\in {\mathcal{C}}^{*}}{w}_G\left(C\right)-|E_1|-|E_2|+|E_1\cup E_2|<\sum _{C\in {\mathcal{C}}^{*}}{w}_G\left(C\right),\hfill \end{array}$$

so contradicting that ${\mathcal{C}}^{*}$ is an optimal solution for $\langle X_G,{\mathcal{S}}_G,w_G\rangle$.

As a consequence of the previous reasoning and of Lemma 6, if ${\mathcal{C}}^{*}$ is an optimal solution for the instance $\langle X_G,{\mathcal{S}}_G,w_G\rangle$ of WSC corresponding to G then the set $I^{*}=\{E\in \overline{\mathcal{E}}:S\left(E\right)\in {\mathcal{C}}^{*}\}$ is an optimal 1-target set for G.

Consider now the following procedure to compute a 1-target set of a signed graph $G=(V,A^{+}\cup A^{-})$: first compute set $\overline{\mathcal{E}}$, then the instance $\langle X,\mathcal{S},w\rangle$ of WSC and, finally apply to it Chvatal’s algorithm in [45] to get a solution $\mathcal{C}=\{S\left(E_1\right),\dots ,S\left(E_k\right)\}$ such that $w_G\left(\mathcal{C}\right)\le (1+log|X_G\left|\right)w_G\left({\mathcal{C}}^{*}\right)$, where ${\mathcal{C}}^{*}$ is an optimal solution for $\langle X_G,{\mathcal{S}}_G,w_G\rangle$.

Needless to say, it may well happen that the sets $E_1,\dots ,E_k$ are not pairwise disjoint, so that the second part of Lemma 6 cannot be exploited to bound the size of the so found 1-target set. In this case, we derive from $\mathcal{C}$ a new set cover ${\mathcal{C}}^{\prime }=\{S\left(E_1^{\prime }\right),\cdots ,S\left(E_h^{\prime }\right)\}$ for $X_G$ such that $w_G\left({\mathcal{C}}^{\prime }\right)\le w_G\left(\mathcal{C}\right)$ and $E_1^{\prime },\dots ,E_h^{\prime }$ are pairwise disjoint: set ${\mathcal{C}}^{\prime }=\mathcal{C}$ and then, while there exist $S\left(E\right),S\left(F\right)\in {\mathcal{C}}^{\prime }$ such that $E\cap F\ne \varnothing$, replace in ${\mathcal{C}}^{\prime }$ the pair $S\left(E\right),S\left(F\right)$ by $S(E\cup F)$. Notice that, at any replacement, ${\mathcal{C}}^{\prime }$ is still a set cover for $\langle X_G,{\mathcal{S}}_G,w_G\rangle$ and its weight does not increase since $w_G\left(S(E\cup F)\right)-(w_G\left(S\left(E\right)\right)+w_G\left(S\left(F\right)\right))=|E\cup F|-\left(\right|E|+|F\left|\right)\le 0.$

Hence, in $poly\left(\right|G|,|\overline{\mathcal{E}}\left|\right)$-time we have computed a 1-target set $I_0=\{E_1^{\prime },\dots ,E_h^{\prime }\}$ for G such that

$$|I_0|=w_G\left({\mathcal{C}}^{\prime }\right)\le w_G\left(\mathcal{C}\right)\le (1+log|X_G\left|\right)w_G\left({\mathcal{C}}^{*}\right)=(1+log|V\left|\right)|I^{*}|.$$

This proves the following theorem.

Theorem 4.

It is possible to find an $(1+log|V\left|\right)$-approximate solution for an instance $G=(V,A^{+}\cup A^{-})$ of 1-USTSS in $poly\left(\right|G|,|\overline{\mathcal{E}}\left|\right)$-time.

In general, the algorithm described so far does not run in polynomial time since the size of $\overline{\mathcal{E}}$ is not polynomially bounded by $\left|G\right|$. Actually, the size of $\overline{\mathcal{E}}$ is strongly related to the topology of $G^{-}$ and in what follows we shall consider topologies yielding families of polynomial size. Without loss of generality, we shall only consider (weakly) connected graphs.

A source tree is a weakly connected directed graph containing one source node s connected to each other node of the graph by exactly one path and such that, for any pair of nodes u and v, if there is a path from u to v then such a path is contained in the path from s to v. Similarly as for the generalized chains, a generalized source tree consists of a set of strongly connected components linked to each other in a source tree-like topology. This means that, if we replace each strongly connected component in $G^{-}$ by a single node, we get a source tree.

Corollary 1.

1-USTSS is $(1+log|V\left|\right)$-approximable for instances $G=(V,A^{+}\cup A^{-})$ such that $G^{-}$ is a source tree or a generalized source tree.

Proof. 

When the graph $G^{-}$ is a (directed) source tree then, for each $u\in V$, $\mathcal{E}\left(u\right)$ is the set of nodes in the subtree of $G^{-}$ rooted at u. Hence, if $\mathcal{E}\left(u\right)\cap \mathcal{E}\left(v\right)\ne \varnothing$ then either $\mathcal{E}\left(u\right)\subseteq \mathcal{E}\left(v\right)$ or $\mathcal{E}\left(v\right)\subseteq \mathcal{E}\left(u\right)$. This proves that $\overline{\mathcal{E}}=\left\{\mathcal{E}\left(u\right)\right|u\in V\}$, that is, $|\overline{\mathcal{E}}|=|V|$.

A similar reasoning to that used in Theorem 3 for the case of the generalized chain allows to extend to generalized trees the result about trees. □

6. Conclusions and Open Problems

This paper aims at studying the impact of negative relations (witnessing antagonism or distrusting) to diffusion processes within a network. We first defined a diffusion rule, generalizing the Linear Threshold Model to signed relations, and then we studied the complexity of computing a minimum size target set with respect to it. We finally considered a set of restrictions under which the problem is approximable to some extent.

Our approximability results all refer to 1-target sets. We proved that the lower bound $(log|V|+1)$ on the approximation ratio is tight for a simple topology of the graph of the negative relations, that is, the generalized source tree, and that our problem is in PO if such graph is a generalized chain. Needless to say, broadening the set of topologies of the graph of the negative relations still yielding reasonable approximation is an interesting research direction. After the results in [3,24], studying the problem restricted to graphs of bounded tree-width or clique-width looks like a worthwhile research direction.

After the discussion in Section 2, we remark that 1-target sets correspond to some kind of dominating sets, that we have called dominating sets with constrained pairs: given a graph $G=(V,E)$ and a set $C\subseteq V\times V$, any node $v\in V$ is dominated by a set $D\subseteq V$ if $v\in D$ or v has a neighbor in D and, for each $(u,v)\in C$, $u\notin D$. We have, thus, proved that the bound $(log|V|+1)$ on the approximation ratio of the Dominating Set problem still holds for our constrained problem when $(V,C)$ is a generalized source tree. Again, broadening the set of topologies of the graph of the negative relations still yielding $O(log|V\left|\right)$-approximation seems an interesting research direction. Finally, our $({\Delta }^{+}+1)$-approximation ratio is exponentially far from the $[log(\Delta +1)+1]$-approximation ratio holding for the minimum Dominating Set problem [43]. Narrowing the gap is an issue deserving attention too.