The algorithm and complexity of co-secure domination in geometric intersection graphs

Given a graph G with vertex set V, a dominating set \(S\subseteq V\) $S\subseteq V$ is a co-secure dominating set of G if for every vertex \(u\in S\) $u\in S$ , there is a vertex \(v\in V{\setminus } S\) $v\in V\backslash S$ adjacent to u such that \((S{\setminus }\{u\})\cup \{v\}\) $(S\backslash \{u\})\cup \{v\}$ is a dominating set of G. The minimum co-secure dominating set (or, for short, MCSDS) problem asks to find an MCSDS in a given graph. In this paper, first we show that the decision version of the problem is NP-complete in grid graphs and supergrid graphs. Consequently, we show that the problem remains NP-complete for unit disk and unit square graphs. Secondly, we show that the MCSDS problem is APX-hard in d-box graphs for any fixed integer \(d\ge 2\) $d\ge 2$ . Finally, we give an \(O(n+m)\) $O(n+m)$ time \(2(t-1)\) $2(t-1)$ -approximation algorithm for the MCSDS problem in several geometric intersection graphs which are \(K_{1,t}\) $K_{1,t}$ -free for some integer \(t\ge 3\) $t\ge 3$ .