License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.4
URN: urn:nbn:de:0030-drops-66274
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6627/
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 sublinear-factor algorithm for the general version, we provide a (sublinear) approximation algorithm for the bounded-round 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 hardness-of-approximation results for the bounded-round version. We show that they translate to general Target Set Selection, leading to a hardness factor of n^(1/2-epsilon) 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^(1-epsilon) 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:1--4:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-018-7},
ISSN = {1868-8969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6627},
URN = {urn:nbn:de:0030-drops-66274},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.4},
annote = {Keywords: target set selection, influence propagation, approximation algorithms, hardness of approximation, planted dense subgraph}
}
|
Keywords: |
|
target set selection, influence propagation, approximation algorithms, hardness of approximation, planted dense subgraph |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
06.09.2016 |
