Skip to main content

On Approximating Target Set Selection

Author(s): Charikar, Moses; Naamad, Yonatan; Wirth, Anthony

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1h249
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCharikar, Moses-
dc.contributor.authorNaamad, Yonatan-
dc.contributor.authorWirth, Anthony-
dc.date.accessioned2021-10-08T19:44:41Z-
dc.date.available2021-10-08T19:44:41Z-
dc.date.issued2016en_US
dc.identifier.citationCharikar, Moses, Yonatan Naamad, and Anthony Wirth. "On Approximating Target Set Selection." Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) 60 (2016): 4:1--4:16. doi:10.4230/LIPIcs.APPROX-RANDOM.2016.4en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1h249-
dc.description.abstractWe 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.en_US
dc.format.extent4:1 - 4:16en_US
dc.language.isoen_USen_US
dc.relation.ispartofApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)en_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleOn Approximating Target Set Selectionen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.APPROX-RANDOM.2016.4-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
ApproximatingTargetSetSelection.pdf624.25 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.