Complexity and approximation of the connected set-cover problem

Abstract

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 delta)-approximation. In addition, one such (1 + ln delta)-approximation algorithm for this problem is proposed. Furthermore, it is proved that there is no polynomial-time -approximation for any for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.