Improved approximation algorithms for $k$-connected $m$-dominating set problems

Abstract

A graph is $k$-connected if it has $k$ internally-disjoint paths between every pair of nodes. A subset $S$ of nodes in a graph $G$ is a $k$-connected set if the subgraph $G[S]$ induced by $S$ is $k$-connected; $S$ is an $m$-dominating set if every $v\in V\setminus S$ has at least $m$ neighbors in $S$. If $S$ is both $k$-connected and $m$-dominating then $S$ is a $k$-connected $m$-dominating set, or $(k,m)$-cds for short. 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. We consider the case $m\ge k$ and obtain the following approximation ratios. For unit disc-graphs we obtain ratio $O(k\ln k)$, improving the previous ratio $O(k^2\ln k)$. For general graphs we obtain the first non-trivial approximation ratio $O(k^2\ln n)$.