  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 \geq 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).
