The complexity of secure domination problem in graphs
Yun-Ping Deng, Haichao Wang, Yancai Zhao · Discussiones Mathematicae Graph Theory · 2017
A dominating set of a graph G is a subset D V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u V (G) \ S has one neighbor v in S such that (S \ {v}) {u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1) ln |V | for any > 0, unless NPDTIME |V | O(log log |V |) . Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.