On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint

Abstract

In the problem of minimum connected dominating set with routing cost constraint, we are given a graph $G=(V,E)$, and the goal is to find the smallest connected dominating set $D$ of $G$ such that, for any two non-adjacent vertices $u$ and $v$ in $G$, the number of internal nodes on the shortest path between $u$ and $v$ in the subgraph of $G$ induced by $D\cup \{u,v\}$ is at most $\alpha$ times that in $G$. For general graphs, the only known previous approximability result is an $O(\log n)$-approximation algorithm ($n=|V|$) for $\alpha =1$ by Ding et al. For any constant $\alpha >1$, we give an $O(n^{1-\frac{1}{\alpha }}(\log n{)}^{\frac{1}{\alpha }})$-approximation algorithm. When $\alpha \ge 5$, we give an $O(\sqrt{n}\log n)$-approximation algorithm. Finally, we prove that, when $\alpha =2$, unless $NP\subseteq DTIME(n^{poly\log n})$, for any constant $\epsilon >0$, the problem admits no polynomial-time $2^{{\log }^{1-\epsilon }n}$-approximation algorithm, improving upon the $\Omega (\log n)$ bound by Du et al. (albeit under a stronger hardness assumption).