Algorithmic Aspects of 2-Secure Domination in Graphs

Let $G(V,E)$ be a simple, undirected and connected graph. A dominating set $S \subseteq V(G)$iscalleda$2$-\mathit{\text{secure}}\mathit{\text{dominating}}\mathit{\text{set}}($2$-SDS)in$G$,ifforeverypairofdistinctvertices$u_1,u_2 \in V(G)$ there exists a pair of distinct vertices $v_1,v_2\in S$ such that $v_1\in N[u_1]$, $v_2 \in N[u_2]$and$(S \setminus {v_1,v_2}) \cup {u_1,u_2 }$ is a dominating set in $G$. The $2$$\mathit{\text{-secure}}\mathit{\text{domination}}\mathit{\text{number}}$ denoted by ${\gamma }_{2s}(G)$, equals the minimum cardinality of a $2$-SDS in $G$. Given a graph $G$ and a positive integer $k,$ the $2$-Secure Domination ($2$-SDM) problem is to check whether $G$ has a $2$-secure dominating set of size at most $k\mathrm{.}$ It is known that $2$-SDM is NP-complete for bipartite graphs. In this paper, we prove that the $2$-SDM problem is NP-complete for planar graphs and doubly chordal graphs, a subclass of chordal graphs. We strengthen the NP-complete result for bipartite graphs, by proving this problem is NP-complete for some subclasses of bipartite graphs namely, star convex bipartite, comb convex bipartite graphs. We prove that $2$-SDM is linear time solvable for bounded tree-width graphs. We also show that the $2$-SDM is W[2]-hard even for split graphs. The Minimum $2$-Secure Dominating Set (M2SDS) problem is to find a $2$-secure dominating set of minimum size in the input graph. We propose a $\mathrm{\Delta }(G)+1$ $-$ approximation algorithm for M2SDS, where $\mathrm{\Delta }(G)$ is the maximum degree of the input graph $G$ and prove that M2SDS cannot be approximated within $(1-ϵ)\ln (\mathrm{\mid }V\mathrm{\mid })$ for any $ϵ>0$ unless $NP\subseteq DTIME(\mathrm{\mid }V{\mathrm{\mid }}^{O(\log \log \mathrm{\mid }V\mathrm{\mid })})$. % even for bipartite graphs. A secure dominating set of a graph $\mathit{\text{defends}}$ one attack at any vertex of the graph. Finally, we show that the M2SDS is APX-complete for graphs with $\mathrm{\Delta }(G)=4.$