Title: Parameterized Complexity of Safe Set,
Abstract: 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 $n^{o(pw)}$ unless the ETH is false, (2) it
admits no polynomial kernel parameterized by the vertex cover number $vc$
unless $\mathrm{PH} = \Sigma^{\mathrm{p}}_{3}$, but (3) it is fixed-parameter
tractable (FPT) when parameterized by the neighborhood diversity $nd$, and (4)
it can be solved in time $n^{f(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.