• 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

Parameterized Complexity of Safe Set

Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019), Parameterized Complexity of Safe Set, in Heggernes, Pinar, Algorithms and Complexity, Proceedings, Springer International Publishing : Berlin Heidelberg, p. 38-49. 10.1007/978-3-030-17402-6_4

View/Open
1901.09434.pdf (679.2Kb)
Type
Communication / Conférence
Date
2019
Conference title
11th International Conference on Algorithms and Complexity (CIAC 2019)
Conference date
2019-05
Conference city
Rome
Conference country
Italy
Book title
Algorithms and Complexity, Proceedings
Book author
Heggernes, Pinar
Publisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-17401-9
Number of pages
378
Pages
38-49
Publication identifier
10.1007/978-3-030-17402-6_4
Metadata
Show full item record
Author(s)
Belmonte, Rémy
autre
Hanaka, Tesshu

Katsikarelis, Ioannis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ono, Hirotaka
Department of Mathematical Informatics
Otachi, Yota
Kumamoto Gakuen University
Abstract (EN)
In this paper we study the problem of finding a small safe set S in a graph G, i.e. a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in G−S. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth pw and cannot be solved in time no(pw) unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number vc unless PH=Σp3, but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity nd, and (4) it can be solved in time nf(cw) for some double exponential function f where cw is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.
Subjects / Keywords
Safe set; Parameterized complexity; Vulnerability parameter; Pathwidth; Clique-width

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Complexity of (A,ℓ)-Path Packing 
    Belmonte, Rémy; Hanaka, Tesshu; Kanzaki, Masaaki; Kiyomi, Masashi; Kobayashi, Yasuaki; Kobayashi, Yusuke; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2022) Article accepté pour publication ou publié
  • Thumbnail
    Independent Set Reconfiguration Parameterized by Modular-Width 
    Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
  • Thumbnail
    Independent Set Reconfiguration Parameterized by Modular-Width 
    Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2020) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Orientable Deletion 
    Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2020) 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