Charikar, Moses ;
Naamad, Yonatan ;
Wirth, Anthony
On Approximating Target Set Selection
Abstract
We study the Target Set Selection (TSS) problem introduced by Kempe, Kleinberg, and Tardos (2003). This problem models the propagation of influence in a network, in a sequence of rounds. A set of nodes is made "active" initially. In each subsequent round, a vertex is activated if at least a certain number of its neighbors are (already) active. In the minimization version, the goal is to activate a small set of vertices initially  a seed, or target, set  so that activation spreads to the entire graph. In the absence of a sublinearfactor algorithm for the general version, we provide a (sublinear) approximation algorithm for the boundedround version, where the goal is to activate all the vertices in r rounds. Assuming a known conjecture on the hardness of Planted Dense Subgraph, we establish hardnessofapproximation results for the boundedround version. We show that they translate to general Target Set Selection, leading to a hardness factor of n^(1/2epsilon) for all epsilon > 0. This is the first polynomial hardness result for Target Set Selection, and the strongest conditional result known for a large class of monotone satisfiability problems. In the maximization version of TSS, the goal is to pick a target set of size k so as to maximize the number of nodes eventually active. We show an n^(1epsilon) hardness result for the undirected maximization version of the problem, thus establishing that the undirected case is as hard as the directed case. Finally, we demonstrate an SETH lower bound for the exact computation of the optimal seed set.
BibTeX  Entry
@InProceedings{charikar_et_al:LIPIcs:2016:6627,
author = {Moses Charikar and Yonatan Naamad and Anthony Wirth},
title = {{On Approximating Target Set Selection}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {4:14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6627},
URN = {urn:nbn:de:0030drops66274},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.4},
annote = {Keywords: target set selection, influence propagation, approximation algorithms, hardness of approximation, planted dense subgraph}
}
2016
Keywords: 

target set selection, influence propagation, approximation algorithms, hardness of approximation, planted dense subgraph 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Issue date: 

2016 
Date of publication: 

2016 