Banerjee, Suman and Mathew, Rogers and Panolan, Fahad
(2022)
Target Set Selection Parameterized by Vertex Cover and More.
Theory of Computing Systems.
ISSN 14324350
Full text not available from this repository.
(
Request a copy)
Abstract
Diffusion is a natural phenomenon in many realworld 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 realworld 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 tau(v) which is a positive integer. A node v will be influenced at time step t', if there are at least tau(v) number of nodes in its neighborhood which have been activated on or before time step t'  1. The diffusion stops when no more nodeactivation is possible. Given a simple, undirected graph G with a threshold function tau : V (G)> N, the TARGET SET SELECTION (TSS) problem is about choosing a minimum cardinality set, say S subset of 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 nonnegative integer i, we say a set T subset of V (G) is a degree i modulator of G if the degree of any vertex in the graph G  T is at most i. Degree0 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:
It was shown by Nichterlein et al. (Soc. Netw. Anal. Min. 3(2), 233256 2013) that it is possible to compute an optimalsized target set in O(2((2t+1) t) .m) time, where t denotes the cardinality of a minimum degree0 modulator of G. We improve this result by designing an algorithm running in time 2(O(t log t)) n.
We design a 2(2O(t)) n(O(1)) time algorithm to compute an optimal target set for G, where t is the size of a minimum degree1 modulator of G.
We show that for a graph on n vertices of treewidth s, the TSS problem cannot be solved in f (s)n(o(s/log s)) time unless the Exponential Time Hypothesis fails. This is an improvement over the previously known lower bound of f (s)n(o(root s)) due to BenZwi et al. (Discret. Optim. 8(1), 8796 2011). In fact, we prove that same lower bound holds when parameterized by treedepth or stardeletion number.
[error in script]
Actions (login required)

View Item 