Approximating k-connected m-dominating sets
share
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-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 ≥ k we obtain the following approximation ratios. For general graphs our ratio O(k n) improves the previous best ratio O(k^2 n) and matches the best known ratio for unit weights. For unit disc graphs we improve the ratio O(k k) to {m/m-k,k^2/3}· O(^2 k) -- this is the first sublinear ratio for the problem, and the first polylogarithmic ratio O(^2 k)/ϵ when m ≥ (1+ϵ)k; furthermore, we obtain ratio {m/m-k,√(k)}· O(^2 k) for uniform weights. These results are obtained by showing the same ratios for the Subset k-Connectivity problem when the set T of terminals is an m-dominating set with m ≥ k.
READ FULL TEXT