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

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}$isatmost$\alpha$timesthatin$G$. For general graphs, the only known previous approximability result is an $O(\log n)$-approximation algorithm ($n=\mathrm{\mid }V\mathrm{\mid }$) 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})$,foranyconstant$\epsilon > 0$, the problem admits no polynomial-time $2^{{\log }^{1-ϵ}n}$-approximation algorithm, improving upon the $\mathrm{\Omega }(\log n)$ bound by Du et al. (albeit under a stronger hardness assumption).