  Let $G(V,E)$ be a simple, undirected and connected graph. A dominating set $S
\subseteq V(G)$ is called a $2$-\textit{secure dominating set} ($2$-SDS) in
$G$, if for every pair of distinct vertices $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$\textit{-secure domination 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.$ 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 $
\Delta(G)+1 $ $ - $ approximation algorithm for M2SDS, where $ \Delta(G) $ is
the maximum degree of the input graph $ G $ and prove that M2SDS cannot be
approximated within $ (1 - \epsilon) \ln(| V | ) $ for any $ \epsilon > 0 $
unless $ NP \subseteq DTIME(| V |^{ O(\log \log | V | )}) $. % even for
bipartite graphs. A secure dominating set of a graph \textit{defends} one
attack at any vertex of the graph. Finally, we show that the M2SDS is
APX-complete for graphs with $\Delta(G)=4.$

Discrete Mathematics;Computational Complexity