Parameterized approximability of maximizing the spread of influence in networks
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014), Parameterized approximability of maximizing the spread of influence in networks, Journal of Discrete Algorithms, 27, p. 54-65. 10.1016/j.jda.2014.05.001
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/1303.6907v2Date
2014Journal name
Journal of Discrete AlgorithmsVolume
27Publisher
Elsevier
Pages
54-65
Publication identifier
Metadata
Show full item recordAbstract (EN)
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value thr(v)thr(v) attached to each vertex v, the spread of influence is modeled as follows: A vertex v becomes “active” (influenced) if at least thr(v)thr(v) of its neighbors are active. In the corresponding optimization problem the objective is then to find a fixed number k of vertices to activate such that the number of activated vertices at the end of the propagation process is maximum. We show that this problem is strongly inapproximable in time f(k)⋅nO(1)f(k)⋅nO(1), for some function f , even for very restrictive thresholds. In the case that the threshold of each vertex equals its degree, we prove that the problem is inapproximable in polynomial time and it becomes r(n)r(n)-approximable in time f(k)⋅nO(1)f(k)⋅nO(1), for some function f, for any strictly increasing function r. Moreover, we show that the decision version parameterized by k is W[1]W[1]-hard but becomes fixed-parameter tractable on bounded degree graphs.Subjects / Keywords
Parameterized complexity; Approximation; Parameterized approximation; Target set selection; Dynamic monopolies; Spread of information; Viral marketingRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013) Communication / Conférence
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chopin, Morgan (2014) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chopin, Morgan; Fellows, Michael R. (2011) Communication / Conférence