# Latency-Bounded Target Set Selection in Signed Networks
## 5 The \(1\)-Ustss Problem
### \(1\)-Ustss and \(G^{-}\)
Notice that, if \(\mathcal{C}^{*}\) is an optimal solution for the instance \(\langle X_{G},\mathcal{S}_{G},w_{G}\rangle\) of WSC corresponding to \(G\) then, for any \(S(E_{1}),S(E_{2})\in\mathcal{C}^{*}\), it holds that \(E_{1}\cap E_{2}=\emptyset\): indeed, if there exist \(S(E_{1}),S(E_{2})\in\mathcal{C}\) such that \(E_{1}\cap E_{2}\
eq\emptyset\), since \(E_{1}\cup E_{2}\in\overline{\mathcal{E}}\) and, thus, \(S(E_{1}\cup E_{2})\in\mathcal{S}_{G}\) and, moreover, \(S(E_{1}\cup S(E_{2})=S(E_{1}\cup E_{2})\), then the set \(\mathcal{C}^{\prime}=\mathcal{C}^{*}-\{S(E_{1}),S(E_{2})\}\cup\{S(E_{1}\cup E _{2})\}\) would still be a set cover for \(X_{G}\) and  
\[\sum_{C\in\mathcal{C}^{\prime}}w_{G}(C) = \sum_{C\in\mathcal{C}*}w_{G}(C)-w_{G}(S(E_{1}))-w_{G}(S(E_{2}))+ w_{G}(S(E_{1}\cup E_{2}))\] \[= \sum_{C\in\mathcal{C}^{*}}w_{G}(C)-|E_{1}|-|E_{2}|+|E_{1}\cup E_{ 2}|<\sum_{C\in\mathcal{C}^{*}}w_{G}(C),\]  
so contradicting that \(\mathcal{C}^{*}\) is an optimal solution for \(\langle X_{G},\mathcal{S}_{G},w_{G}\rangle\). As a consequence of the previous reasoning and of Lemma 6, if \(\mathcal{C}^{*}\) is an optimal solution for the instance \(\langle X_{G},\mathcal{S}_{G},w_{G}\rangle\) of WSC corresponding to \(G\) then the set \(I^{*}=\{E\in\overline{\mathcal{E}}:S(E)\in\mathcal{C}^{*}\}\) is an optimal \(1\)-target set for \(G\). Consider now the following procedure to compute a \(1\)-target set of a signed graph \(G=(V,A^{+}\cup A^{-})\): first compute set \(\overline{\mathcal{E}}\), then the instance \(\langle X,\mathcal{S},w\rangle\) of WSC and, finally apply to it [PERSON]'s algorithm in [45] to get a solution \(\mathcal{C}=\{S(E_{1}),\ldots,S(E_{k})\}\) such that \(w_{G}(\mathcal{C})\leq(1+\log|X_{G}|)w_{G}(\mathcal{C}^{*})\), where \(\mathcal{C}^{*}\) is an optimal solution for \(\langle X_{G},\mathcal{S}_{G},w_{G}\rangle\). Needless to say, it may well happen that the sets \(E_{1},\ldots,E_{k}\) are not pairwise disjoint, so that the second part of Lemma 6 cannot be exploited to bound the size of the so found \(1\)-target set. In this case, we derive from \(\mathcal{C}\) a new set cover \(\mathcal{C}^{\prime}=\{S(E^{\prime}_{1}),\ldots,S(E^{\prime}_{h})\}\) for \(X_{G}\) such that \(w_{G}(\mathcal{C}^{\prime})\leq w_{G}(\mathcal{C})\) and \(E^{\prime}_{1},\ldots,E^{\prime}_{h}\) are pairwise disjoint: set \(\mathcal{C}^{\prime}=\mathcal{C}\) and then, while there exist \(S(E),S(F)\in\mathcal{C}^{\prime}\) such that \(E\cap F\
eq\emptyset\), replace in \(\mathcal{C}^{\prime}\) the pair \(S(E),S(F)\) by \(S(E\cup F)\). Notice that, at any replacement, \(\mathcal{C}^{\prime}\) is still a set cover for \(\langle X_{G},\mathcal{S}_{G},w_{G}\rangle\) and its weight does not increase since \(w_{G}(S(E\cup F))-(w_{G}(S(E))+w_{G}(S(F)))=|E\cup F|-(|E|+|F|)\leq 0\). Hence, in \(poly(|G|,|\overline{\mathcal{E}}|)\)-time we have computed a \(1\)-target set \(I_{0}=\{E^{\prime}_{1},\ldots,E^{\prime}_{h}\}\) for \(G\) such that  
\[|I_{0}|=w_{G}(\mathcal{C}^{\prime})\leq w_{G}(\mathcal{C})\leq(1+\log|X_{G}|)w_{ G}(\mathcal{C}^{*})=(1+\log|V|)|I^{*}|.\]  
This proves the following theorem. **Theorem 4**. : _It is possible to find an \((1+\log|V|)\)-approximate solution for an instance \(G=(V,A^{+}\cup A^{-})\) of 1-USTSS in \(poly(|G|,|\overline{\mathcal{E}}|)\)-time._  
In general, the algorithm described so far does not run in polynomial time since the size of \(\overline{\mathcal{E}}\) is not polynomially bounded by \(|G|\). Actually, the size of \(\overline{\mathcal{E}}\) is strongly related to the topology of \(G^{-}\) and in what follows we shall consider topologies yielding families of polynomial size. Without loss of generality, we shall only consider (weakly) connected graphs. A source tree is a weakly connected directed graph containing one source node \(s\) connected to each other node of the graph by exactly one path and such that, for any pair of nodes \(u\) and \(v\), if there is a path from \(u\) to \(v\) then such a path is contained in the path from \(s\) to \(v\).