I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct vertices in $I$ is more than $2$. In other words $I$ is $2$-independent in $G$ if and only if $I$ is independent in $G^2$, the square of $G$. $2$-independent sets are also sometimes called $2$-packings, packings or closed neighborhood packings.The maximum $2$-independent set problems ask for the $2$-independence set with maximum cardinality in a given graphs $G$. In [1] it is proved that for any $\epsilon > 0$ it can't be approximated with a better than $O(n^{1/2-\epsilon})$ multiplicative factor (this problem is called maximum distance-$3$ independent set in this paper). However, I did not find any positive results about its approximation. Is there any $O(\sqrt{n})$-approximation (or worse) algorithm? Or, maybe, there are better inapproximability results?Also, any results about characterization of the squares of all graphs may help (let us denote the class of squares of all graphs as $\mathcal{G}^{(2)}$). For example, it may occur that $\mathcal{G}^{(2)}$ is a subclass of some class where maximum independent set problem admits some approximation. Or, conversely, it may be a superclass of some class with no approximation better than $n^{1-\epsilon}$. Unfortunately, I am not aware of any such results.[1] Eto, Hiroshi and Guo, Fengrui and Miyano, Eiji. Distance-$d$ Independent Set Problems for Bipartite and Chordal Graphs // Combinatorial Optimization and Applications, Vol. 7402 (2012), pages 234-244.
Approximation algorithms for the maximum $2$-independence set problem
graph theory;approximation algorithms;approximation hardness
An $O(\sqrt n)$-approximation greedy algorithm for this problem is presented in the paper Independent sets with domination constraints by Magns M. Halldrsson, Jan Kratochvl, Jan Arne Tellec (Discrete Applied Mathematics, Vol. 99, Issues 13, Pages 3954). 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.