• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

The Robust Set Problem: Parameterized Complexity and Approximation

Bazgan, Cristina; Chopin, Morgan (2012), The Robust Set Problem: Parameterized Complexity and Approximation, in Widmayer, Peter, Mathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings, Springer : Berlin Heidelberg, p. 136-147. 10.1007/978-3-642-32589-2_15

View/Open
mfcs12.pdf (354.6Kb)
Type
Communication / Conférence
Date
2012
Conference title
37th International Symposium on Mathematical Foundations of Computer Science , MFCS 2012
Conference date
2012-08
Conference city
Bratislava
Conference country
Slovakia
Book title
Mathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings
Book author
Widmayer, Peter
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-32588-5
Pages
136-147
Publication identifier
10.1007/978-3-642-32589-2_15
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chopin, Morgan
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In 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.
Subjects / Keywords
Robust set

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized Complexity of the Firefighter Problem 
    Bazgan, Cristina; Chopin, Morgan; Fellows, Michael R. (2011) Communication / Conférence
  • Thumbnail
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence
  • Thumbnail
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
  • Thumbnail
    Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation 
    Chopin, Morgan (2013-07) Thèse
  • Thumbnail
    Parameterized Complexity of Firefighting 
    Bazgan, Cristina; Chopin, Morgan; Cygan, Marek; Fellows, Michael R.; Fomin, Fedor V.; van Leeuwen, Erik Jan (2014) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo