2023/06/17 by Panda, B S, Rana, Soumyashree, Mishra, Sounaka
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2306.10378
A set D ⊆ V of a graph G=(V, E) is a dominating set of G if every vertex v∈ V∖ D is adjacent to at least one vertex in D. A set S ⊆ V is a co-secure dominating set (CSDS) of a graph G if S is a dominating set of G and for each vertex u ∈ S there exists a vertex v ∈ V∖ S such that uv ∈ E and (S∖ \u\) ∪ \v\ is a dominating set of G. The minimum cardinality of a co-secure dominating set of G is the co-secure domination number and it is denoted by γcs(G). Given a graph G=(V, E), the minimum co-secure dominating set problem (Min Co-secure Dom) is to find a co-secure dominating set of minimum cardinality. In this paper, we strengthen the inapproximability result of Min Co-secure Dom for general graphs by showing that this problem can not be approximated within a factor of (1- ε)ln |V| for perfect elimination bipartite graphs and star convex bipartite graphs unless P=NP. On the positive side, we show that Min Co-secure Dom can be approximated within a factor of O(ln |V|) for any graph G with δ(G)≥ 2. For 3-regular and 4-regular graphs, we show that Min Co-secure Dom is approximable within a factor of \dfrac83 and \dfrac103, respectively. Furthermore, we prove that Min Co-secure Dom is APX-complete for 3-regular graphs.