# Latency-Bounded Target Set Selection in Signed Networks
## 3 Model and Problems Definitions  
A signed graph \(G=(V,A^{+}\cup A^{-})\) is the overlapping of two directed graphs, \(G^{+}=(V,A^{+})\) and \(G^{-}=(V,A^{-})\), over the same set of nodes. For an example of the definitions to follow, refer to Figure 1.  
For any \(u\in V\), we denote as \(N^{+}_{in}(u)\) and \(N^{-}_{in}(u)\), respectively, the sets of _in-friends_ and of _in-enemies_ of \(u\), that is, the in-neighbors of \(u\) in \(G^{+}\) and in \(G^{-}\):  
\[N^{+}_{in}(u)=\{v\in V:(v,u)\in A^{+}\}\quad\text{ and }\quad N^{-}_{in}(u)=\{v \in V:(v,u)\in A^{-}\}.\]  
Similarly, for each \(u\in V\), we define the sets of out-friends and out-enemies of \(u\) as  
\[N^{+}_{out}(u)=\{v\in V:(u,v)\in A^{+}\}\quad\text{ and }\quad N^{-}_{out}(u)=\{v \in V:(u,v)\in A^{-}\}.\]  
A path in \(G^{+}\) between any pair of nodes in \(V\) is called a positive path and \(D^{+}\) denotes the maximum length of a shortest positive path. For \(u\in V\), we denote as \(\pi^{+}(u)\) the set of nodes such that, for any \(v\in\pi^{+}(u)\), \(G\) contains a positive path from \(v\) to \(u\) and, for \(v\in\pi^{+}(u)\), as \(d^{+}(v,u)\) the length of a shortest positive path in \(G\) from \(v\) to \(u\). Finally, for \(u\in V\) and \(V^{\prime}\subseteq V\),  
\[d^{+}(V^{\prime},u)=\left\{ \begin{array}{ll}\min\{d^{+}(v,u):v\in V^{\prime }\cap\pi^{+}(u)\}&\quad\text{ if }V^{\prime}\cup\pi^{+}(u)\
eq\emptyset,\\ D^{+}+1&\quad\text{ otherwise.}\end{array} \right.\]  
Negative paths, \(D^{-}\), \(\pi^{-}(u)\), \(d^{-}(u,v)\) and \(d^{-}(V^{\prime},u)\) are defined similarly. Let \(\theta:V\to\mathbb{N}^{+}\) and \(w:A^{+}\cup A^{-}\to\mathbb{N}^{+}\) be, respectively, a node-weight and an arc-weight function. A set \(I_{0}\subseteq V\) of initially informed nodes (all the remaining nodes in \(V-I_{0}\) being unaware) may eventually start a \((\theta,w)\)-_diffusion process_: at time step \(1\) any node \(u\in V-I_{0}\) becomes informed if the cumulative weight of its in-friends is at least \(\theta(u)\) while the cumulative weight of its in-enemies is less than \(\theta(u)\), that is  
\[\sum_{v\in N_{in}^{+}(u)\cap I_{0}}w(v,u)\geq\theta(u)\quad\text{ and }\quad\sum_{v\in N _{in}^{-}(u)\cap I_{0}}w(v,u)<\theta(u);\]  
We denote as \(I_{1}\) the set of nodes becoming informed at time step \(1\). Conversely, if the cumulative weight of \(u\)'s in-enemies is at least \(\theta(u)\), then the negative influence that \(u\) receives from \(N_{in}^{-}(u)\) will induce it to remain in the unaware state forever, that is, at any successive time step \(u\) will never become informed. We say \(u\) becomes refractory. Needless to say, if neither the cumulative weight of \(u\)'s in-friends nor the cumulative weight of \(u\)'s in-enemies reaches \(\theta(u)\), \(u\) does not change its state. Inductively, if \(I_{j}\) denotes the set of nodes becoming informed at time step \(j\), an unaware node \(u\in V-\cup_{j=0}^{t-1}I_{j}\) becomes refractory at time step \(t>1\) if  
\[\sum_{v\in N_{in}^{-}(u)\cap(I_{0}\cup I_{1}\cup\dots\cup I_{t-1})}w(v,u)\geq \theta(u), \tag{1}\]  
while it becomes informed if (1) does not hold and  
\[\sum_{v\in N_{in}^{+}(u)\cap(I_{0}\cup I_{1}\cup\dots\cup I_{t-1})}w(v,u)\geq \theta(u).\]  
A set \(I_{0}\subseteq V\) is a _target set_ for \(\langle G=(V,A^{+}\cup A^{-}),\theta,w\rangle\) if \(\cup_{t\geq 0}I_{t}=V\). Needless to say, the size of a target set \(I_{0}\subseteq V\) is \(|I_{0}|\). The Signed Target Set Selection problem (STSS) asks for computing a minimum size target set for a given signed graph \(G=(V,A^{+}\cup A^{-})\) with node- and arc-weight functions \(\theta\) and \(w\). The Unweighted Signed Target Set Selection problem (USTSS) is the restriction of STSS in which all node- and arc-weights equal 1. Notice that, if \(I_{t}=\emptyset\) for some \(t\geq 0\), then \(I_{s}=\emptyset\) for all \(s>t\). The _latency_ of a diffusion process is, therefore, defined as the integer \(t\in\mathbb{N}^{+}\) such that \(I_{t}\
eq\emptyset\) and \(I_{t+1}=\emptyset\).