Disjoint Dominating and 2-Dominating Sets in Graphs: Hardness and Approximation results

Abstract

A set $D\subseteq V$ of a graph $G=(V,E)$ is a dominating set of $G$ if each vertex $v\in V\setminus D$ is adjacent to at least one vertex in $D,$ whereas a set $D_2\subseteq V$ is a $2$-dominating (double dominating) set of $G$ if each vertex $v\in V\setminus 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 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 $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. 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, that this problem can not be approximated within $n^{\frac{1}{6}-\epsilon }$ for any $\epsilon >0,$ unless P=NP.

17 pages, 3 figures, submitted to discrete optimisation