On the complexity of co-secure dominating set problem

A set D⊆V of a graph G=(V,E) is a dominating set of G if every vertex v∈V∖D is adjacent to at least one vertex in D. A set S⊆V is a co-secure dominating set (CSDS) of a graph G if S is a dominating set of G and for each vertex u∈S there exists a vertex v∈V∖S such that uv∈E and (S∖{u})∪{v} is a dominating set of G. The minimum cardinality of a co-secure dominating set of G is the co-secure domination number and it is denoted by γcs(G). Given a graph G=(V,E), the minimum co-secure dominating set problem (Min Co-secure Dom) is to find a co-secure dominating set of minimum cardinality. In this paper, we strengthen the inapproximability result of Min Co-secure Dom for general graphs by showing that this problem can not be approximated within a factor of (1−ε)ln⁡|V| for perfect elimination bipartite graphs and star convex bipartite graphs unless P=NP. On the positive side, we show that Min Co-secure Dom can be approximated within a factor of O(ln⁡|V|) for any graph G with δ(G)≥2. For 3-regular and 4-regular graphs, we show that Min Co-secure Dom is approximable within a factor of 83 and 103, respectively. Furthermore, we prove that Min Co-secure Dom is APX-complete for 3-regular graphs.