Approximating k-Connected m-Dominating Sets
Zeev Nutov · Algorithmica · 2022
A subset S of nodes in a graph G is a k-connected m-dominating set ((k , m)-cds) if the subgraph G[S] induced by S is k-connected and every $$v \in V {\setminus } S$$ has at least m neighbors in S. In the k -Connected m -Dominating Set ((k , m)-CDS) problem, the goal is to find a minimum weight (k, m)-cds in a node-weighted graph. For $$m \ge k$$ we obtain the following approximation ratios. For unit disk graphs we improve the ratio $$O(k \ln k)$$ of Nutov (Inf Process Lett 140:30–33, 2018) to $$\min \left\{ \frac{m^2}{(m-k+1)^2},k^{2/3}\right\} \cdot O(\ln ^2 k)$$ —this is the first sublinear ratio for the problem, and the first polylogarithmic ratio $$O(\ln ^2 k)/\epsilon ^2$$ when $$m \ge (1+\epsilon )k$$ ; furthermore, we obtain ratio $$\min \left\{ \frac{m}{m-k+1},\sqrt{k}\right\} \cdot O(\ln ^2 k)$$ for uniform weights. For general graphs our ratio $$O(k \ln n)$$ improves the previous best ratio $$O(k^2 \ln n)$$ of Nutov (2018) and matches the best known ratio for unit weights of Zhang et al. (INFORMS J Comput 30(2):217–224, 2018). These results are obtained by showing the same ratios for the Subset k -Connectivity problem when the set of terminals is an m-dominating set.