# Latency-Bounded Target Set Selection in Signed Networks
## 5 The \(1\)-Ustss Problem
### \(1\)-Ustss and \(G^{-}\)  
Let \(G=(V,A^{+}\cup A^{-})\) be a signed graph. Notice that any \(I\subseteq V\) is a target set for \(G\) only if, for each \(u\in I\), it holds that \(N_{out}^{-}(u)\subseteq I\). In turn, if \(I\) is a target set for \(G\) containing \(u\) and, hence, \(N_{out}^{-}(u)\), then \(I\) must contain also \(N_{out}^{-}(v)\), for any \(v\in N_{out}^{-}(u)\). More precisely, if we define, for each \(u\in V\), the set \(\mathcal{E}(u)\) containing \(u\) and all the nodes reachable from \(u\) by a path in \(G^{-}\), that is,  
\[\mathcal{E}(u)=\{u\}\cup\{v\in V:u\in\pi^{-}(v)\},\]  
then the next fact holds, which follows from the previous observation by a simple inductive argument. **Fact 1:**_If \(I\subseteq V\) is a target set for \(G=(V,A^{+}\cup A^{-})\) then, for any \(u\in I\), \(\mathcal{E}(u)\subseteq I\)._  
Observe now that, if \(G^{-}\) is strongly connected, then, for any \(u\in V\), it holds that \(\mathcal{E}(u)=V\); hence, by Fact 1, we get  
**Fact 2:**_If \(G^{-}\) is strongly connected, then the only target set for \(G\) (no matter about its latency) is \(V\)._  
For any \(E\subseteq V\), we define the set  
\[S(E)=E\cup\{u\in V:d^{+}(E,u)=1\}=E\cup\{u\in V:\exists z\in E\cap N_{in}^{+ }(u)\},\]  
that is, the set of nodes that are or may become informed within time step 1 whenever all nodes in \(E\) are contained in the set of the initially informed nodes. Lemma 5: \(I\subseteq V\) _is a \(1\)-target set for \(G=(V,A^{+}\cup A^{-})\) if and only if \(S(I)=V\) and, for any \(u\in I\), \(\mathcal{E}(u)\subseteq I\)._Proof. : If \(I\subseteq V\) is a \(1\)-target set for \(G=(V,A^{+}\cup A^{-})\), then, trivially, \(S(I)=V\) and, by Fact 1, for any \(u\in I\), \(\mathcal{E}(u)\subseteq I\). Conversely, suppose that \(S(I)=V\) and, for any \(u\in I\), \(\mathcal{E}(u)\subseteq I\). Then, for any node \(x\in V-I\),  
* since \(S(I)=V\), there exists \(y\in I\) such that \((y,x)\in A^{+}\) (that is, \(y\) may inform \(x\) at time step 1) and, furthermore,
* since for any \(u\in I\), \(\mathcal{E}(u)\subseteq I\), then, for any \(z\in V\) such that \((z,x)\in A^{-}\), since \(x\in\pi^{-}(z)\) and \(x\
ot\in I\), \(z\
ot\in I\) (that is, any node that could forbid \(x\) to become informed is not in \(I\)). Lemma 5 allows us to prove membership to PO of \(1\)-USTSS when restricted to chain and generalized chain graphs. The chain graph over the node set \(V=\{v_{1},\ldots,v_{n}\}\) is made of the set of arcs \(\{(v_{j},v_{j-1}):j=2,\ldots,n\}\). A generalized chain graph consists of a set \(C_{1},\ldots,C_{n}\) of strongly connected components linked to each other in a chain-like topology, that is, for any \(j=2,\ldots,n-1\) and for any \(u\in C_{j}\), arc \((u,v)\) exists only if \(v\in C_{j-1}\). Theorem 5.1: _The \(1\)-USTSS problem restricted to instances \(G=(V,A^{+}\cup A^{-})\) such that \(G^{-}=(V,A^{-})\) is a chain or a generalized chain graph is in PO._  
Proof. : If \(G^{-}\) is a chain, that is, \(V=\{v_{1},\ldots,v_{n}\}\) and \(A^{-}=\{(v_{j},v_{j-1}):j=2,\ldots,n\}\), then \(\mathcal{E}(v_{1})=\{v_{1}\}\), \(\mathcal{E}(v_{2})=\{v_{1},v_{2}\}=\{v_{2}\}\cup\mathcal{E}(v_{1})\) and, in general, for \(i\geq 2\), \(\mathcal{E}(v_{i})=\{v_{i}\}\cup\mathcal{E}(v_{i-1})\). Hence, \(\mathcal{E}(v_{1})\subseteq\cdots\subseteq\mathcal{E}(v_{n})\). Correspondingly, \(S(\mathcal{E}(v_{1}))\subseteq\cdots\subseteq S(\mathcal{E}(v_{n}))\): indeed, for any \(i=1,\ldots,n-1\),  
\[S(\mathcal{E}(v_{i}))=\mathcal{E}(v_{i})\cup\{u\in V:\exists z\in\mathcal{E}( v_{i})\cap N^{+}_{in}(u)\}\subseteq\mathcal{E}(v_{i+1})\cup\{u\in V: \exists z\in\mathcal{E}(v_{i+1})\cap N^{+}_{in}(u)\}.\]  
As a consequence, by Lemma 5, \(\mathcal{E}(v_{m})\) is a minimum size \(1\)-target set for \(G\), where \(m=\min\{j\in\{1,\ldots,n\}:S(\mathcal{E}(v_{j}))=V\}\). Let \(G^{-}\) be a generalized chain and let \(C_{1},\ldots,C_{n}\) be its strongly connected components.