Constant Thresholds Can Make Target Set Selection Tractable

Target Set Selection , which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful polynomial-time approximation as well as fixed-parameter algorithms. Given an undirected graph, the task is to select a mi...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2014-07, Vol.55 (1), p.61-83
Main Authors: Chopin, Morgan, Nichterlein, André, Niedermeier, Rolf, Weller, Mathias
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Approximation
Computer Science
Distributed processing
Graphs
Islands
Mathematical analysis
Parametrization
Social network analysis
Social networks
Studies
Tasks
Theory of Computation
Thresholds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Target Set Selection , which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful polynomial-time approximation as well as fixed-parameter algorithms. Given an undirected graph, the task is to select a minimum number of vertices into a “target set” such that all other vertices will become active in the course of a dynamic process (which may go through several activation rounds). A vertex, equipped with a threshold value  t , becomes active once at least  t of its neighbors are active; initially, only the target set vertices are active. We contribute further insights into the existence of islands of tractability for Target Set Selection by spotting new parameterizations characterizing some sparse graphs as well as some “cliquish” graphs and developing corresponding fixed-parameter tractability and (parameterized) hardness results. In particular, we demonstrate that upper-bounding the thresholds by a constant may significantly alleviate the search for efficiently solvable, but still meaningful special cases of Target Set Selection .
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-013-9499-3