Disjoint dominating and 2-dominating sets in graphs: Hardness and approximation results

A set D ⊆ V of a graph G = ( V , E ) is a dominating set of G if each vertex v ∈ V ∖ D is adjacent to at least one vertex in D , whereas a set D 2 ⊆ V is a 2-dominating (double dominating) set of G if each vertex v ∈ V ∖ D 2 is adjacent to at least two vertices in D 2 . A graph G is a D D 2 -graph if there exists a pair ( D , D 2 ) of dominating set and 2-dominating set of G which are disjoint. In this paper, we give approximation algorithms for the problem of determining a minimal spanning D D 2 -graph of minimum size ( Min- D D 2 ) with an approximation ratio of 3; a minimal spanning D D 2 -graph of maximum size ( Max- D D 2 ) with an approximation ratio of 3; and for the problem of adding minimum number of edges to a graph G to make it a D D 2 -graph ( Min-to- D D 2 ) with an O ( log n ) approximation ratio. The above three results answer the open problems mentioned in the paper, Miotk et al. (2020). Furthermore, we prove that Min- D D 2 and Max- D D 2 are APX -complete for graphs with maximum degree 4 . We also show that Min- D D 2 and Max- D D 2 are approximable within a factor of 1.8 and 1.5, respectively, for any 3-regular graph. Finally, we show the inapproximability result of Max-Min-to- D D 2 for bipartite graphs: this problem cannot be approximated within n 1 6 − ɛ for any ɛ > 0 , unless P=NP .