On the Complexity of Co-secure Dominating Set Problem

Abstract

A set $D\subseteq V$ of a graph $G=(V,E)$ is a dominating set of $G$ if every vertex $v\in V\setminus D$ is adjacent to at least one vertex in $D.$ A set $S\subseteq 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\in S$ there exists a vertex $v\in V\setminus S$ such that $uv\in E$ and $(S\setminus \{u\})\cup \{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 ${\gamma }_{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-\epsilon )\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 $\delta (G)\ge 2$. For $3$-regular and $4$-regular graphs, we show that Min Co-secure Dom is approximable within a factor of $\frac{8}{3}$ and $\frac{10}{3}$, respectively. Furthermore, we prove that Min Co-secure Dom is APX-complete for $3$-regular graphs.

12 pages, 2 figures