# Latency-Bounded Target Set Selection in Signed Networks
## 1 Introduction
Other interesting cases in which the problems become tractable are studied in [16]. In [3], [PERSON] et al. proved that the problem can be solved in time \(O(M^{w}|V|)\) where \(M\) is the maximum threshold value and \(w\) is the treewidth of the graph: since \(M\) cannot exceed the maximum node degree, this proves that the problem is fixed-parameter tractable if parametrized with respect to both treewidth and the maximum node degree of the graph. The aforementioned papers did not consider the issue of the number of time steps necessary for the feature diffusion. However, this is a relevant point in many settings: in viral marketing, for instance, it is quite important to spread information quickly. Indeed, research in Behavioural Economics shows that humans make decisions mostly on the basis of very recent events [28; 29]; furthermore, marketing strategies are more effective when the time needed to reach all the target individuals is short. Hence, it is a worthwhile goal to study diffusion processes while taking into account the number of time steps within which it is required to have all the nodes informed and, actually, this topic has already received some attention. Indeed, as pointed out by the authors, the inapproximability result proved in [13] for general graphs still holds when the diffusion process is required to end in a bounded number of time steps (16 time steps, in fact). In [24] a polynomial-time algorithm spreading a feature over a set of required size within a constant number of time steps in graphs of bounded clique-width has been proposed. Following [24], in this paper, diffusion processes with an available fixed number of time steps within which informing all the nodes will be called latency-bounded diffusion processes. All diffusion rules considered so far assume that nodes are always positively influenced by their neighbors, that is, any node always has increased its support in favor of the feature being spread throughout the network whenever one of its neighbors becomes informed. However, in most network settings also negative link effects are to be considered. One way to take into account negative feedbacks is that pursued in [30; 31; 32; 33] where it is assumed that individuals may also develop a negative opinion about the feature to be spread and, in this case, they may negatively influence their neighbors. In [30] a generalization of the Independent Cascade model is proposed in which each initiator turns positive (experiencing good quality of the feature) with probability \(q\) and turns negative (disliking the feature) with probability \(1-q\), and then, at each time step, a node having become positively informed in the previous step tries to inform each of its unaware neighbors: if successful (with success probability \(p\)) the neighbor becomes positively informed with probability \(q\) and negatively informed with probability \(1-q\); meanwhile, a negatively informed node in the previous step tries to negatively inform its unaware neighbors, and if successful the neighbors become negatively informed. In [33], instead, a generalization of the Linear Thresholdmodel is proposed in which each node (which can be inactive, positively active or negatively active) \(v\) has a belief score \(r(v)\) (measuring the amount of trust that the node places on its own judgment) and a threshold \(\theta(v)\), and each arc has a weight \(w(u,v)\); a node is activated the first time the sum of weights from its active neighbors plus its own belief score exceeds its threshold and, after being activated, the node decides on its attitude (positive or negative) based on the ratio between the positive influence (sum of weights from positively activated friends) and negative influence (sum of weights from negatively activated friends). A different approach to negative feedbacks is tackled in [34; 35] taking into account the possibility that some relations between individuals are ruled by, for instance, antagonism and distrusting (see [36] and references quoted therein).