Show simple item record

The Robust Set Problem: Parameterized Complexity and Approximation

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorChopin, Morgan*
dc.date.accessioned2013-09-05T11:04:28Z
dc.date.available2013-09-05T11:04:28Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11625
dc.descriptionLNCS n°7464
dc.language.isoenen
dc.subjectRobust set
dc.subject.ddc003en
dc.titleThe Robust Set Problem: Parameterized Complexity and Approximation
dc.typeCommunication / Conférence
dc.description.abstractenIn this paper, we introduce the Robust Set problem: given a graph G = (V,E), a threshold function t:V → N and an integer k, find a subset of vertices V′ ⊆ V of size at least k such that every vertex v in G has less than t(v) neighbors in V′. This problem occurs in the context of the spread of undesirable agents through a network (virus, ideas, fire, …). Informally speaking, the problem asks to find the largest subset of vertices with the property that if anything bad happens in it then this will have no consequences on the remaining graph. The threshold t(v) of a vertex v represents its reliability regarding its neighborhood; that is, how many neighbors can be infected before v gets himself infected.We study in this paper the parameterized complexity of Robust Set and the approximation of the associated maximization problem. When the parameter is k, we show that this problem is W[2]-complete in general and W[1]-complete if all thresholds are constant bounded. Moreover, we prove that, if P ≠ NP, the maximization version is not n 1 − ε - approximable for any ε > 0 even when all thresholds are at most two. When each threshold is equal to the degree of the vertex, we show that k -Robust Set is fixed-parameter tractable for parameter k and the maximization version is APX-complete. We give a polynomial-time algorithm for graphs of bounded treewidth and a PTAS for planar graphs. Finally, we show that the parametric dual problem (n − k)-Robust Set is fixed-parameter tractable for a large family of threshold functions.
dc.identifier.citationpages136-147
dc.relation.ispartoftitleMathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings
dc.relation.ispartofeditorWidmayer, Peter
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2012
dc.relation.ispartofurl10.1007/978-3-642-32589-2
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-32588-5
dc.relation.conftitle37th International Symposium on Mathematical Foundations of Computer Science , MFCS 2012
dc.relation.confdate2012-08
dc.relation.confcityBratislava
dc.relation.confcountrySlovakia
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-642-32589-2_15
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-23T09:33:40Z
hal.faultCode{"duplicate-entry":{"hal-01505586":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
mfcs12.pdf
Size:
354.6Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record