2012 | OriginalPaper | Buchkapitel
Constant Thresholds Can Make Target Set Selection Tractable
verfasst von : Morgan Chopin, André Nichterlein, Rolf Niedermeier, Mathias Weller
Erschienen in: Design and Analysis of Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 approximation as well as fixed-parameter algorithms. The task is to select a minimum number of vertices into a “target set” such that all other vertices will become active in course of a dynamic process (which may go through several activation rounds). A vertex, which is 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 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
.