Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Parameterized Approximability of Maximizing the Spread of Influence in Networks
verfasst von : Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.