# Latency-Bounded Target Set Selection in Signed Networks
## 5 The \(1\)-Ustss Problem
### \(1\)-Ustss and \(G^{-}\)
As already stated in the observation leading to Fact 2, for any \(j=1,\ldots,n\) and for any \(u,v\in C_{j}\), it holds that \(\mathcal{E}(u)=\mathcal{E}(v)\): hence, in what follows we shall use the notation \(\mathcal{E}_{j}\) to refer to any set \(\mathcal{E}(u)\) for \(u\in C_{j}\). By the same argument holding for chain graphs, for any \(j=1,\ldots,n\), we get that \(\mathcal{E}_{j}\) contains all nodes in any \(C_{i}\) with \(i\leq j\). Hence, again by a similar reasoning to that holding in the chain case, since \(\mathcal{E}_{1}\subseteq\cdots\subseteq\mathcal{E}_{n}\), we get that \(\mathcal{E}_{m}\) is a minimum size \(1\)-target set for \(G\), where \(m=\min\{j\in\{1,\ldots,n\}:S(\mathcal{E}_{j})=V\}\). Lemma 5 shows that any \(1\)-target set is actually obtained by choosing a subcollection of sets in the collection \(\mathcal{E}=\{\mathcal{E}(u):u\in V\}\). We now introduce the collection \(\overline{\mathcal{E}}\) as the closure of \(\mathcal{E}\) under non-empty intersections: that is, \(\mathcal{E}\subseteq\overline{\mathcal{E}}\), and, for each \(E_{1}\), \(E_{2}\in\overline{\mathcal{E}}\) such that \(E_{1}\cap E_{2}\
eq\emptyset\), \(E_{1}\cup E_{2}\in\overline{\mathcal{E}}\). The introduction of \(\overline{\mathcal{E}}\) allows us to describe any target set for \(G\) as the union of pairwise disjoint subsets, that is:  
**Fact 3**: _For any target set \(I\) for \(G=(V,A^{+}\cup A^{-})\), there exists \(\mathcal{B}\subseteq\overline{\mathcal{E}}\) such that \(I=\cup_{\mathcal{B}\in\mathcal{B}}B\) and, for any \(B_{1}\), \(B_{2}\in\mathcal{B}\), \(B_{1}\cap B_{2}=\emptyset\)._  
Based on fact 3, we now show how to get in over polynomial time a \((1+\log|V|)\)-approximate solution for \(1\)-USTSS by a (non-polynomial-time) reduction from \(1\)-USTSS to minimum Weighted Set Cover (WSC) and by the \((1+\log|V|)\)-approximation algorithm for WSC [45]. Later in this section, we shall discuss cases in which the procedure overall runs in polynomial time. Recall that an instance of WSC is a triple \(\langle X,\mathcal{S},w\rangle\) where \(\mathcal{S}\subseteq 2^{X}\), \(\cup_{S\in\mathcal{S}}S=X\), and \(w:\mathcal{S}\to\mathbb{N}^{+}\); the goal is finding a minimum weight set \(\mathcal{C}\subseteq\mathcal{S}\) such that \(\bigcup_{\mathcal{C}\in\mathcal{C}}C=X\), where the weight of \(\mathcal{C}\) is defined as \(w(\mathcal{C})=\sum\limits_{C\in\mathcal{C}}w(\mathcal{C})\). Let \(G=(V,A^{+}\cup A^{-})\) be a signed graph; the corresponding instance \(\langle X_{G},\mathcal{S}_{G},w_{G}\rangle\) of WSC is obtained by setting \(X_{G}=V\), \(\mathcal{S}_{G}=\{S(E):E\in\overline{\mathcal{E}}\}\) and, for each \(E\in\overline{\mathcal{E}}\), \(w_{G}(S(E))=|E|\). **Lemma 6**: _Let \(G=(V,A^{+}\cup A^{-})\) be a signed graph and \(E_{1},\ldots,E_{k}\in\overline{\mathcal{E}}\); \(I_{0}=\cup_{j=1}^{k}E_{j}\), is a \(1\)-target set for \(G\) if and only if \(\mathcal{C}=\{S(E_{1}),\ldots,S(E_{k})\}\) is a set cover for \(X_{G}\). Furthermore, if \(E_{1},\ldots,E_{k}\) are pairwise disjoint then \(|I_{0}|=w_{G}(\mathcal{C})\)._  
Let \(E_{1},\ldots,E_{k}\) be elements of \(\overline{\mathcal{E}}\) and let \(I_{0}=\cup_{j=1}^{k}E_{j}\). By definition, \(I_{0}\) is a \(1\)-target set for \(G\) if and only if \(S(I_{0})=V\). Hence,  
\[S(I_{0})=\bigcup_{j=1}^{k}S(E_{j})=V=X_{G},\]  
that is, \(\mathcal{C}=\{S(E_{1}),\ldots,S(E_{k})\}\) is a set cover of \(X\). If \(E_{1},\ldots,E_{k}\) are pairwise disjoint, then  
\[|I_{0}|=\left|\bigcup_{j=1}^{k}E_{j}\right|=\sum_{j=1}^{k}|E_{j}|=\sum_{j=1}^{ k}w_{G}(S(E_{j}))=w_{G}(\mathcal{C}).\]  
The previous lemma shows that the proposed transformation is actually a reduction and that, if a \(1\)-target set for \(G\) is described as the union of pairwise disjoint elements of \(\overline{\mathcal{E}}\), then its size equals the weight of the corresponding set cover of \(X_{G}\).