# Latency-Bounded Target Set Selection in Signed Networks
## 1 Introduction  
The study of diffusion processes is a widely investigated topic in the complex networks setting. It aims at analyzing how local interactions among nearby nodes may lead to the diffusion, possibly over the whole network, of some feature (opinion/information/disease) starting from a limited set of initiator (or seed) nodes. The problem known as Influence Maximization has been introduced by [PERSON] and [PERSON] [1; 2] for the design of viral marketing campaigns on social networks by using a small (let us say, given) number of initiators (for example by providing a limited set of people free samples of a product to be merchandised), starting from which a cascade is triggered maximizing the overall spreading of information (see also [3; 4; 5; 6; 7; 8; 9]). Dually, the target set selection problem aims at finding out a minimum size set of initiators able to spread the feature over the whole network [3; 10; 11; 12; 13; 14; 15; 16; 17] or over a large (let us say, given) portion of the network; such a set of initiators is called a target set. Diffusion processes are usually modeled by graphs in which each vertex may be in one out of two states: informed or unaware. Initially, only nodes in a given set \(l_{0}\) are informed, while all the others are unaware; while the diffusion process goes on, nodes may change their states according to the diffusion rule of the process. A diffusion rule may be reversible, if changes from informed to unaware are allowed, or irreversible if a node can no longer change its state once it becomes informed. In a discrete diffusion model, nodes (eventually) change their state at discrete time steps. In the rest of this paper, we shall only deal with discrete irreversible diffusion processes. Several rules to govern the transition from unaware to informed have been proposed, and many papers have studied the dynamics of these systems mostly in stochastic scenarios (see [18; 19] and references quoted therein). In the Independent Cascade Model [6; 20] an edge-weighted graph is assumed and, as soon as a node \(u\) becomes informed, each currently unaware neighbor \(v\) of \(u\) changesits state to informed with probability equal to the ratio between the weight of arc \((u,v)\) and the sum of weights of all arcs incident on \(u\). A deterministic counterpart of this model is that of a _Majority Process_[21; 22; 23] in which, at each time step, a vertex changes its state if and only if at least half of its neighbors are in the opposite state. The Linear Threshold Model [5; 6; 24; 25; 26] is based on the association of a threshold \(\theta(v)\) to each node \(v\) and of a weight \(w(u,v)\) to each arc \((u,v)\): node \(u\) becomes informed if and only if \(\sum_{v\in N(u)\cap I}w(u,v)\geq\theta(u)\), where \(N(u)\) is the set of neighbors of \(u\) and \(I\) is the set of the already informed nodes. In other words, the Linear Threshold Model assumes that any unaware node becomes informed if the weight of its informed neighbors is above a certain threshold (i.e., the node is subject to a large enough amount of \"social pressure\"). In [25; 27] a special case of the Linear Threshold Model is considered, in which all arc weights are \(1\) and all nodes have the same threshold \(\theta\); in this case, the threshold value just stands for the number of neighbors that have to be informed in order to induce a node to become informed. In that paper, the authors prove that deciding if a graph has a target set of size \(d\) is an NP-complete problem for \(\theta\geq 3\). [PERSON] [13] then strengthened such result by showing the NP-hardness of the problem even for \(\theta=2\) and proved that, in the same hypothesis, no polynomial-time algorithm exists with approximation factor better than \(O(2\log^{1-c}|V|)\) also when all nodes have constant degrees, unless \(\mathrm{NP}\subseteq DTIME(n^{polylog})\); in the same paper a polynomial-time algorithm to find an optimal solution has been provided when the underlying graph is a tree.