# Latency-Bounded Target Set Selection in Signed Networks
## 4 Complexity of Approximation of USTSS and \(2\)-USTSS
### Ustss\(\leq_{A}\)weakly positive-minimum ones
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}}(x_{u})=\left\{ \begin{array}{ll}\texttt{true}&\text{if }u\in V^{ \prime},\\ \texttt{false}&\text{if }u\in V-V^{\prime}.\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^{+}(u)\cap I_{0}\
eq\emptyset\): let \(z_{u}\in\pi^{+}(u)\cap I_{0}\) be such that \(d^{+}(z_{u},u)=\min\{d^{+}(w,u):w\in\pi^{+}(u)\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}(u)\), let \(y_{v}\in\pi^{+}(v)\cap I_{0}\) be such that \(d^{+}(y_{v},v)=\min\{d^{+}(w,v):w\in\pi^{+}(v)\cap I_{0}\}\): by Lemma 3, for any \(v\in N^{-}_{in}(u)\), \(d^{+}(z_{u},u)\leq d_{V}(y_{v},v)\) and, hence, for any \(v\in N^{-}_{in}(u)\), and for any \(w\in\pi^{+}(v)\cap I_{0}\), \(x_{z_{u}}\) is contained in every clause in \(Q_{u}\) containing \(\
eg x_{w}\). As a consequence, every clause \(c\in Q_{u}\) containing \(\
eg x_{w}\) as its negative variable such that \(a_{I_{0}}(x_{w})=\texttt{true}\), also contains \(x_{z_{u}}\); since \(z_{u}\in I_{0}\), \(a(x_{z_{u}})=\texttt{true}\) and, hence, \(c\) is satisfied by \(a_{I_{0}}\). This proves that every clause \(c\in Q_{u}\) containing \(\
eg x_{w}\) as its negative variable such that \(a(x_{w})=\texttt{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^{+}(u)\) such that \(a(x_{z})=\texttt{true}\) and, hence, \(z\in I_{0}\). This implies that \(\pi^{+}(u)\cap I_{0}\
eq\emptyset\). Furthermore, for any \(u\in V-I_{0}\) and \(v\in N^{-}_{in}(u)\), and for any \(y\in\pi^{+}(v)\cap I_{0}\) (that is, \(a_{I_{0}}(x_{y})=\texttt{true}\) and \(v\) may become informed by a path from \(y\)), any clause in \(Q_{u}\) containing \(\
eg x_{y}\) has also to contain a positive variable \(x_{z}\) such that \(a_{I_{0}}(x_{z})=\texttt{true}\). By construction of the clauses in \(Q_{u}\), this implies that \(d^{+}(z,u)\leq d^{+}(y,v)\), that is, \(d^{+}(I_{0},u)\leq d^{+}(I_{0},v)\). By Lemma 3, this proves that \(I_{0}\) is a target set for \(G\).