Target Set Selection Parameterized by Vertex Cover and More

Diffusion is a natural phenomenon in many real-world networks. Spreading of ideas, rumors in an online social network; propagation of virus, malware in a computer network; spreading of diseases in a human contact network, etc. are some real-world examples of this. Diffusion often starts from a set of initial nodes known as seed nodes. A node can be in any one of the following two states: influenced (active) or not influenced (inactive). We assume that a node can change its state from inactive to active, however, not vice versa. Only the seed nodes are active initially and the information is dissipated from these seed nodes in discrete time steps. Each node v is associated with a threshold value τ(v) which is a positive integer. A node v will be influenced at time step \(t^{\prime }\), if there are at least τ(v) number of nodes in its neighborhood which have been activated on or before time step \(t^{\prime }-1\). The diffusion stops when no more node-activation is possible. Given a simple, undirected graph G with a threshold function \(\tau :V(G) \rightarrow \mathbb {N}\), the Target Set Selection (TSS) problem is about choosing a minimum cardinality set, say \(S \subseteq V(G)\), such that starting a diffusion process with S as its seed set will eventually result in activating all the nodes in G. For any non-negative integer i, we say a set \(T\subseteq V(G)\) is a degree-i modulator of G if the degree of any vertex in the graph G − T is at most i. Degree-0 modulators of a graph are precisely its vertex covers. Consider a graph G on n vertices and m edges. We have the following results on the TSS problem: