
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
Type
Communication / ConférenceDate
2019Conference title
11th International Conference on Algorithms and Complexity (CIAC 2019)Conference date
2019-05Conference city
RomeConference country
ItalyBook title
Algorithms and Complexity, ProceedingsBook author
Heggernes, PinarPublisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-17401-9
Number of pages
378Pages
38-49
Publication identifier
Metadata
Show full item recordAuthor(s)
Belmonte, Rémyautre
Hanaka, Tesshu
Katsikarelis, Ioannis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael

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-widthRelated items
Showing items related by title and author.
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
-
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é
-
Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
-
Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2020) Article accepté pour publication ou publié
-
Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2020) Article accepté pour publication ou publié