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 $\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 fixed-parameter 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 clique-width. We also present (5) a faster fixed-parameter algorithm when parameterized by the solution size.