2023/12/02 by Rana, Soumyashree, Mishra, Sounaka, Panda, Bhawani Sankar
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2312.01149
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 D2⊆ V is a 2-dominating (double dominating) set of G if each vertex v∈ V ∖ D2 is adjacent to at least two vertices in D2. A graph G is a DD2-graph if there exists a pair (D, D2) of dominating set and 2-dominating set of G which are disjoint. In this paper, we solve some open problems posed by M.Miotk, J.~Topp and P.Żyliński (Disjoint dominating and 2-dominating sets in graphs, Discrete Optimization, 35:100553, 2020) by giving approximation algorithms for the problem of determining a minimal spanning DD2-graph of minimum size (Min-DD2) with an approximation ratio of 3; a minimal spanning DD2-graph of maximum size (Max-DD2) with an approximation ratio of 3; and for the problem of adding minimum number of edges to a graph G to make it a DD2-graph (Min-to-DD2) with an O(log n) approximation ratio. Furthermore, we prove that Min-DD2 and Max-DD2 are APX-complete for graphs with maximum degree 4. We also show that Min-DD2 and Max-DD2 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-DD2 for bipartite graphs, that this problem can not be approximated within n(1)/(6)-ε for any ε >0, unless P=NP.