Approximating k-Connected m-Dominating Sets

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∈ V\ S has at least m neighbors in S. In the k-Connectedm-Dominating Set ((k, m)-CDS) problem, the goal is to find a minimum weight (k, m)-cds in a node-weighted graph. For m≥ k we obtain the following approximation ratios. For unit disk graphs we improve the ratio O(kln k) of Nutov (Inf Process Lett 140:30–33, 2018) to min{m2(m-k+1)2,k2/3}·O(ln2k)—this is the first sublinear ratio for the problem, and the first polylogarithmic ratio O(ln ²k) / ϵ² when m≥ (1 + ϵ) k; furthermore, we obtain ratio min{mm-k+1,k}·O(ln2k) for uniform weights. For general graphs our ratio O(kln n) improves the previous best ratio O(k²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 Subsetk-Connectivity problem when the set of terminals is an m-dominating set.