Complexity and approximation of the connected set-cover problem

In this paper, we study the computational complexity and approximation complexity of the connected set-cover problem. We derive necessary and sufficient conditions for the connected set-cover problem to have a polynomial-time algorithm. We also present a sufficient condition for the existence of a (1 +  ln δ)-approximation. In addition, one such (1 +  ln δ)-approximation algorithm for this problem is proposed. Furthermore, it is proved that there is no polynomial-time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${O(\log^{2-\varepsilon} n)}$$\end{document} -approximation for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varepsilon\,{>}\,0}$$\end{document} for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.