Parameterized Approximability of Maximizing the Spread of Influence in Networks
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013), Parameterized Approximability of Maximizing the Spread of Influence in Networks, in Ding-Zhu Du, Guochuan Zhang, Computing and Combinatorics. 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings, Springer : Berlin Heidelberg, p. 543-554. 10.1007/978-3-642-38768-5_48
Type
Communication / ConférenceExternal document link
http://arxiv.org/abs/1303.6907v2Date
2013Book title
Computing and Combinatorics. 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. ProceedingsBook author
Ding-Zhu Du, Guochuan ZhangPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-38767-8
Pages
543-554
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chopin, Morgan
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Nichterlein, André
Berlin University of Technology
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this paper, we consider the problem of maximizing the spread of influence through a social network. Here, we are given a graph G = (V,E), a positive integer k and a threshold value thr(v) attached to each vertex v ∈ V. The objective is then to find a subset of k vertices to “activate” such that the number of activated vertices at the end of a propagation process is maximum. A vertex v gets activated if at least thr(v) of its neighbors are. We show that this problem is strongly inapproximable in fpt-time with respect to (w.r.t.) parameter k even for very restrictive thresholds. For unanimity thresholds, we prove that the problem is inapproximable in polynomial time and the decision version is W[1]-hard w.r.t. parameter k. On the positive side, it becomes r(n)-approximable in fpt-time w.r.t. parameter k for any strictly increasing function r. Moreover, we give an fpt-time algorithm to solve the decision version for bounded degree graphs.Subjects / Keywords
TSSRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
-
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