Show simple item record

Parameterized Inapproximability of Target Set Selection and Generalizations

dc.contributor.authorBazgan, Cristina
dc.contributor.authorChopin, Morgan
dc.contributor.authorNichterlein, André
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
dc.date.accessioned2016-09-22T15:12:42Z
dc.date.available2016-09-22T15:12:42Z
dc.date.issued2014
dc.identifier.issn2211-3568
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15823
dc.language.isoenen
dc.subjectparameterized complexity
dc.subjectparameterized approximation
dc.subjecttarget set selection
dc.subjectspread of information
dc.subject.ddc003en
dc.titleParameterized Inapproximability of Target Set Selection and Generalizations
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper, we consider the TARGET SET SELECTION problem: given a graph and a threshold value thr(v) for each vertex v of the graph, find a minimum size vertex-subset to “activate” such that all vertices of the graph are activated at the end of the propagation process. A vertex v is activated during the propagation process if at least thr(v) of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions f and ρ this problem cannot be approximated within a factor of ρ(k) in f(k)·nO(1) time, unless FPT=W[P], even for restricted thresholds (namely constant and majority thresholds), where k is the number of vertices to activate in the beginning. We also study the cardinality constraint maximization and minimization versions of the problem for which we prove similar hardness results.
dc.relation.isversionofjnlnameComputability
dc.relation.isversionofjnlvol3
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages135-145
dc.relation.isversionofdoi10.3233/COM-140030
dc.identifier.urlsitehttps://arxiv.org/abs/1403.3565v2
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-23T09:27:25Z
hal.identifierhal-01370527*
hal.version1*
hal.update.actionupdateMetadata*
hal.update.actionupdateFiles*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record