• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Parameterized Complexity of Safe Set

Thumbnail
View/Open
1901.09434.pdf (679.2Kb)
Date
2019
Dewey
Programmation, logiciels, organisation des données
Sujet
Safe set; Parameterized complexity; Vulnerability parameter; Pathwidth; Clique-width
DOI
http://dx.doi.org/10.1007/978-3-030-17402-6_4
Conference name
11th International Conference on Algorithms and Complexity (CIAC 2019)
Conference date
05-2019
Conference city
Rome
Conference country
Italy
Book title
Algorithms and Complexity, Proceedings
Author
Heggernes, Pinar
Publisher
Springer International Publishing
Publisher city
Berlin Heidelberg
Year
2019
Pages number
378
ISBN
978-3-030-17401-9
Book URL
10.1007/978-3-030-17402-6
URI
https://basepub.dauphine.fr/handle/123456789/20328
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Belmonte, Rémy
115536 autre
Hanaka, Tesshu
status unknown
Katsikarelis, Ioannis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ono, Hirotaka
228737 Department of Mathematical Informatics
Otachi, Yota
58827 Kumamoto Gakuen University
Type
Communication / Conférence
Item number of pages
38-49
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.