# Latency-Bounded Target Set Selection in Signed Networks
## 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 4.1: _For any \(\epsilon>0\), \(2\)-USTSS (and, hence, USTSS) is NP-hard to approximate to within \(2^{\log^{1-\epsilon}|V|}\)._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},\ldots,x_{n}\}\) be a set of boolean variables; a set of clauses (i.e., disjunction of literals) \(f=\{c_{1},\ldots,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},\ldots,x_{n}\}\) is a set of boolean variables and \(f=\{c  
* 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 \(-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 \(|f|\). 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}|\leq|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_{m}^{+}(u)\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}\
eq\emptyset\). Suppose there exists \(i\in\{1,\ldots,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}^{-}(\overline{u}_{i})=\emptyset\), \(u_{i}\) is able to inform \(\overline{u}_{i}\). Finally, since \(N_{out}^{+}(\overline{u}_{i})=\emptyset\), \(\overline{u}_{i}\) is unable to inform any node, this proves that \(I-\{\overline{u}_{i}\}\) is still a target set for \(G\). So, \(I_{1}=I-V_{\overline{X}}\) is a target set for \(G\).