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}$ 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^{polylog 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).

تحميل البحث