Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorChopin, Morgan
dc.contributor.authorNichterlein, André
dc.contributor.authorSikora, Florian
dc.date.accessioned2016-06-14T11:24:41Z
dc.date.available2016-06-14T11:24:41Z
dc.date.issued2014
dc.identifier.issn1570-8667
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15557
dc.language.isoenen
dc.subjectParameterized complexity
dc.subjectApproximation
dc.subjectParameterized approximation
dc.subjectTarget set selection
dc.subjectDynamic monopolies
dc.subjectSpread of information
dc.subjectViral marketing
dc.subject.ddc003en
dc.titleParameterized approximability of maximizing the spread of influence in networks
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value thr(v)thr(v) attached to each vertex v, the spread of influence is modeled as follows: A vertex v becomes “active” (influenced) if at least thr(v)thr(v) of its neighbors are active. In the corresponding optimization problem the objective is then to find a fixed number k of vertices to activate such that the number of activated vertices at the end of the propagation process is maximum. We show that this problem is strongly inapproximable in time f(k)⋅nO(1)f(k)⋅nO(1), for some function f , even for very restrictive thresholds. In the case that the threshold of each vertex equals its degree, we prove that the problem is inapproximable in polynomial time and it becomes r(n)r(n)-approximable in time f(k)⋅nO(1)f(k)⋅nO(1), for some function f, for any strictly increasing function r. Moreover, we show that the decision version parameterized by k is W[1]W[1]-hard but becomes fixed-parameter tractable on bounded degree graphs.
dc.relation.isversionofjnlnameJournal of Discrete Algorithms
dc.relation.isversionofjnlvol27
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages54-65
dc.relation.isversionofdoi10.1016/j.jda.2014.05.001
dc.identifier.urlsitehttps://arxiv.org/abs/1303.6907v2
dc.relation.isversionofjnlpublisherElsevier
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:28:18Z
hal.person.labIds989*
hal.person.labIds215382*
hal.person.labIds129314*
hal.person.labIds989*
hal.identifierhal-01331692*


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