# Latency-Bounded Target Set Selection in Signed Networks
## 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^{-\epsilon}|V|}\) for any \(\epsilon>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 worthwhileto 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\
ot\in D\) and \(v\
ot\in D\).