Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00528
Parameterized Complexity of Safe Set
Vol. 24, no. 3, pp. 215245, 2020. Regular paper.
Abstract In this paper we study the problem of finding a small safe set $S$ in a graph $G$,
i.e., a nonempty 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 $\mathsf{pw}$ and cannot be solved in time $n^{o(\mathsf{pw})}$ unless the ETH is false,
(2) it admits no polynomial kernel parameterized by the vertex cover number $\mathsf{vc}$ unless $\mathrm{PH} = \Sigma^{\mathrm{p}}_{3}$, but
(3) it is fixedparameter tractable (FPT) when parameterized by the neighborhood diversity $\mathsf{nd}$, and
(4) it can be solved in time $n^{f(\mathsf{cw})}$ for some double exponential function $f$ where $\mathsf{cw}$ is the cliquewidth.
We also present (5) a faster fixedparameter algorithm when parameterized by the solution size.

Submitted: June 2019.
Reviewed: December 2019.
Revised: February 2020.
Accepted: April 2020.
Final: April 2020.
Published: April 2020.
Communicated by
Alexander Wolff

Journal Supporters
