The safe set problem on particular graph classes

Let $G = (V,E)$ be a connected undirected graph with $n=|V|$ and $m = |E|$. We denote as $G[T]$ the subgraph induced on $G$ by a subset of vertices $T \subseteq V$ and as $\mathcal{C}_G(T)$ the collection of all maximal connected components in $G[T]$. The \emph{Safe Set Problem} (\emph{SSP}) amounts to finding a minimum cardinality nonempty set of vertices $S \subseteq V$ such that each component induced by $S$ has a cardinality not smaller than that of any adjacent component induced by $U = V \setminus S$. This paper provides new results, based on the matching between lower bounds and feasible solutions, for grids, complete bipartite graphs, and windmill graphs. Moreover, it investigates the asymptotic structure of optimal solutions for random graphs. We prove that, for a sufficiently large density, such instances become intrinsically easy as the size of the graph increases, with an optimum equal to $\left\lceil n/2 \right\rceil$, whereas they are generally unfeasible for small densities. This explains the empirical behaviour observed in algorithmic studies.