# Latency-Bounded Target Set Selection in Signed Networks
## 4 Complexity of Approximation of USTSS and \(2\)-USTSS
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}^{-}(v_{j})\subset V_{\overline{X}}\), and since \(I_{1}\cap V_{\overline{X}}=\emptyset\), then \(u_{i}\) is able to inform \(v_{j}\). Since \(N_{out}^{+}(v_{j})=\emptyset\), \(v_{j}\) is unable to inform any other node, and, hence, \(I_{1}-\{v_{j}\}\) 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 \(\leq_{A}\)USTSS. Lemma 2: _For any \(k\in\mathbb{N}^{+}\), with \(1\leq k\leq n\), \(f\) is satisfiable by assigning_ 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 true to \(k\geq 1\) variables in \(X\). We show that the set \(I_{0}=\{u_{i}\in V_{X}:a(x_{i})=\texttt{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(x_{i})=\texttt{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 false to \(u_{h}\) or by assigning 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(x_{i})=\left\{ \begin{array}{ll}\texttt{true}&\text{if $u_{i}\in I_{0}$,}\\ \texttt{false}&\text{if $u_{i}\
ot\in I_{0}$.}\end{array} \right.\]  
Let \(c_{j}\) be a positive clause in \(f\). If, \(u_{i}\
ot\in 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(x_{i})=\texttt{true}\). Let \(c_{j}\) be a negative clause in \(f\), let \(x_{h}\) be its negative variable and let \(x_{j_{1}},\ldots,x_{j_{q}}\) be its positive variables. If \(a(x_{j_{i}})=\texttt{false}\) for any \(i=1,\ldots,q\), and, hence, \(\{u_{j_{1}},\ldots,u_{j_{q}}\}\cap I_{0}=\emptyset\), then, as already noticed, \(v_{j}\) could become informed only at time step 2. In this case it must be \(u_{h}\
ot\in 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\).