Show simple item record

dc.contributor.authorChopin, Morgan
dc.contributor.authorNichterlein, André
dc.contributor.authorNiedermeier, Rolf
dc.contributor.authorWeller, Mathias
HAL ID: 16443
ORCID: 0000-0002-9653-3690
dc.date.accessioned2014-08-28T13:21:35Z
dc.date.available2014-08-28T13:21:35Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/13880
dc.language.isoenen
dc.subjectSpread of influenceen
dc.subjectDynamics in social networksen
dc.subjectParameterized complexityen
dc.subjectKernelizationen
dc.subject.ddc003en
dc.titleConstant Thresholds Can Make Target Set Selection Tractableen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenTarget 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.en
dc.relation.isversionofjnlnameTheory of Computing Systems
dc.relation.isversionofjnlvol55en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages61-83en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s00224-013-9499-3en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record