
Parameterized Complexity of Safe Set
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019), Parameterized Complexity of Safe Set, Journal of Graph Algorithms and Applications, 24, 3, p. 215-245. 10.7155/jgaa.00528
View/ Open
Type
Article accepté pour publication ou publiéDate
2019Journal name
Journal of Graph Algorithms and ApplicationsVolume
24Number
3Publisher
Brown University
Pages
215-245
Publication identifier
Metadata
Show full item recordAuthor(s)
Belmonte, RémyLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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
Otachi, Yota
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 fixed-parameter algorithm when parameterized by the solution size.Subjects / Keywords
Parameterized complexityRelated items
Showing items related by title and author.
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
-
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é
-
Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2018) Communication / Conférence