Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a max{d∗,2d∗−6}-approximate solution to the problem in O(min{d∗,|V|}d∗|V|2) time, while we also show that there exists an instance for which it provides no better than a (d∗−1)-approximate solution. Especially, in the case of d∗⩽4, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to d∗⩽4.