Approximation algorithms for the maximum $2$-independence set problem
An $O(\sqrt n)$-approximation greedy algorithm for this problem is presented in the paper "Independent sets with domination constraints" by Magnús M. Halldórsson, Jan Kratochvı́l, Jan Arne Tellec (Discrete Applied Mathematics, Vol. 99, Issues 1–3, Pages 39–54). The algorithm is greedy: it consequently selects to the output solution a vertex with minimum degree, such that the output solution is still $2$-independent. Thus, the lower and the upper bounds for this problem coincide.