Algorithmic aspects of 2-secure domination in graphs

Let G(V, E) be a simple, connected and undirected graph. A dominating set $$S \subseteq V$$ S ⊆ V is called a 2-secure dominating set (2-SDS) in G, if for each pair of distinct vertices $$v_1,v_2 \in V$$ v 1 , v 2 ∈ V there exists a pair of distinct vertices $$u_1,u_2 \in S$$ u 1 , u 2 ∈ S such that $$u_1 \in N[v_1]$$ u 1 ∈ N [ v 1 ] , $$u_2 \in N[v_2]$$ u 2 ∈ N [ v 2 ] and $$(S {\setminus } \{u_1,u_2\}) \cup \{v_1,v_2 \}$$ ( S \ { u 1 , u 2 } ) ∪ { v 1 , v 2 } is a dominating set in G. The size of a minimum 2-SDS in G is said to be 2-secure domination number denoted by $$\gamma _{2s}(G)$$ γ 2 s ( G ) . The 2-SDM problem is to check if an input graph G has a 2-SDS S, with $$ \vert S \vert \le k$$ | S | ≤ k , where $$ k \in \mathbb {Z}^+ $$ k ∈ Z + . It is proved that for bipartite graphs 2-SDM is NP-complete. 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 reinforce the existing NP-complete result for bipartite graphs, by proving 2-SDM is NP-complete for some subclasses of bipartite graphs specifically, comb convex bipartite and star convex bipartite graphs. We prove that this problem 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 M2SDS problem is to find a 2-SDS of minimum size in the given graph. We give a $$ \varDelta +1 $$ Δ + 1 -approximation algorithm for M2SDS, where $$ \varDelta $$ Δ is the maximum degree of the given graph and prove that M2SDS cannot be approximated within $$ (1 - \epsilon ) \ln (\vert V \vert ) $$ ( 1 - ϵ ) ln ( | V | ) for any $$ \epsilon > 0 $$ ϵ > 0 unless $$ NP \subseteq DTIME(\vert V \vert ^{ O(\log \log \vert V \vert )}) $$ N P ⊆ D T I M E ( | V | O ( log log | V | ) ) . Finally, we prove that the M2SDS is APX-complete for graphs with $$\varDelta =4.$$ Δ = 4 .