Algorithmic aspects of 2-secure domination in graphs

Let G ( V ,  E ) be a simple, connected and undirected graph. A dominating set S ⊆ V is called a 2- secure dominating set (2-SDS) in G , if for each pair of distinct vertices v 1 , v 2 ∈ V there exists a pair of distinct vertices u 1 , u 2 ∈ S such that u 1 ∈ N [ v 1 ] , u 2 ∈ N [ v 2 ] and ( S \ {...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2021-07, Vol.42 (1), p.56-70
Main Authors: Jakkepalli, Pavan Kumar, Palagiri, Venkata Subba Reddy
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Approximation
Codes
Combinatorics
Convex and Discrete Geometry
Graphs
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G ( V ,  E ) be a simple, connected and undirected graph. A dominating set S ⊆ V is called a 2- secure dominating set (2-SDS) in G , if for each pair of distinct vertices v 1 , v 2 ∈ V there exists a pair of distinct vertices u 1 , u 2 ∈ S such that u 1 ∈ N [ v 1 ] , u 2 ∈ N [ v 2 ] and ( 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 γ 2 s ( G ) . The 2-SDM problem is to check if an input graph G has a 2-SDS S , with | S | ≤ k , where 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 Δ + 1 -approximation algorithm for M2SDS, where Δ is the maximum degree of the given graph and prove that M2SDS cannot be approximated within ( 1 - ϵ ) ln ( | V | ) for any ϵ > 0 unless N P ⊆ D T I M E ( | V | O ( log log | V | ) ) . Finally, we prove that the M2SDS is APX-complete for graphs with Δ = 4 .
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-021-00739-9