Seminar by Tony Wirth: On Approximating Target Set Selection

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－ε) for all ε > 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－ε) hardness result for the undirected maximization version of the problem, thus establishing that the undirected case is as hard as the directed case.

Tony Wirth is Associate Professor at The University of Melbourne. Also an alumnus of Melbourne, he completed a PhD at Princeton on approximation algorithms for clustering. Tony’s research also includes text compression, streaming algorithms, and algorithm engineering. His favourite problems are Set Cover, Correlation Clustering and Dictionary-Based Compression. In 2015–6, Tony was Interim Director of the Melbourne School of Information.