# Latency-Bounded Target Set Selection in Signed Networks
## 4 Complexity of Approximation of USTSS and \(2\)-USTSS
### Ustss\(\leq_{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^{+}(u)\cap I_{0}\
eq\emptyset\)_, and_
* _for any_ \(v\in N_{in}^{-}(u)\)_, it holds that_ \(d^{+}(I_{0},u)\leq 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^{\prime}\)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\leq 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},\ldots,I_{D^{+}}\) such that all individual-nodes in \(I_{t}\) become informed at time step \(t\), for any \(1\leq t\leq D^{+}\). This implies that, for any \(t=1,\ldots,D^{+}\) and for any \(u\in I_{t}\), \(d^{+}(I_{0},u)=t\) and, hence, \(\pi^{+}(u)\cap I_{0}\
eq\emptyset\). Let \(u\in I_{t}\), for some \(t=1,\ldots,D^{+}\): if there exists \(v\in N_{in}^{-}(u)\cap I_{s}\) for some \(s\leq t-1\), \(v\) would forbid \(u\) to get influenced at time step \(t\). Hence, for any \(v\in N_{in}^{-}(u)\), it must hold that \(v\in\cup_{s\geq t}I_{s}\), that is, \(d^{+}(I_{0},u)\leq d^{+}(I_{0},v)\). This proves the first part of the assertion. Conversely, suppose that, for any \(u\in V-I_{0}\), \(\pi^{+}(u)\cap I_{0}\
eq\emptyset\) and, for any \(v\in N_{in}^{-}(u)\), it holds that \(d^{+}(I_{0},u)\leq d^{+}(I_{0},v)\). For any \(1\leq t\leq 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}^{-}(u)\cap I_{0}=\emptyset\) by hypothesis, all nodes in \(V_{1}\) are influenced at time step 1. Inductively, it can then be proved that, for any \(t\leq 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^{+}(u)\) be the set \(\{v_{1},\ldots,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}\lor x_{v_{1}}\lor x_{v_{2}}\vee\ \cdots\lor 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}^{-}(u)\). For each \(v\in N_{in}^{-}(u)\), \(Q_{u}\) contains the clause  
\[(\
eg x_{v}\lor x_{u})\]and, for each \(1\leq t\leq D^{+}\) and for each \(z\in\pi^{+}(v)\) such that \(d^{+}(z,v)=t\), \(Q_{u}\) contains the clause  
\[(\
eg x_{z}\lor x_{u}\lor x_{w_{1}}\lor x_{w_{2}}\vee\ \cdots\lor x_{w_{k}}),\]  
where \(\{w_{1},w_{2},\ldots,w_{k}\}=\{w\in V:d^{+}(w,u)\leq 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\).