Safe sets in graphs: Graph classes and structural parameters

A safe set of a graph (G=(V,E)) is a non-empty subset S of V such that for every component A of G[S] and every component B of (G[V {setminus } S]), we have (|A| ge |B|) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.