Advertisement
Published in:
2014 | OriginalPaper | Chapter
Parameterized Inapproximability of Target Set Selection and Generalizations
Authors : Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
Published in: Language, Life, Limits
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we consider the
Target Set Selection
problem: given a graph and a threshold value
for each vertex
v
of the graph, find a minimum size vertex-subset to “activate” s.t. all the vertices of the graph are activated at the end of the propagation process. A vertex
v
is activated during the propagation process if at least
of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions
f
and
ρ
this problem cannot be approximated within a factor of
ρ
(
k
) in
f
(
k
) ·
n
O
(1)
time, unless
FPT
=
W
[
P
], even for restricted thresholds (namely constant and majority thresholds). We also study the cardinality constraint maximization and minimization versions of the problem for which we prove similar hardness results.