<p>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.</p>

CC BY-SA 3.0
2015-12-27T00:14:07.247Z
2015-12-27T00:14:07.247Z
Andrew Ryzhikov
<p>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 <em>$2$-independent</em> 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.</p>

<p>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 &gt; 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?</p>

<p>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.</p>

<p>[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.</p>

CC BY-SA 3.0
2015-11-07T22:02:47.427Z
Since *every* graph is (isomorphic to) an induced subgraph of the square  of some graph, the class $\mathcal{G}^2$ of squares of *all* graphs $G$ gives no hope in studying Max $2$-independece 
set in *arbitrary* graphs $G$, I think. By the way, there exists no good characterization for $\mathcal{G}^2$ as proved by 
Motwani and Sudan that recognizing if a given graph is the square of some graph is NP-complete, 
see [here](http://www.sciencedirect.com/science/article/pii/0166218X94000239).
vb le
CC BY-SA 3.0
2015-11-07T22:28:06.030Z
@vble could you please give me a reference for the first result you mentioned? I suppose, that this result does not give a direct answer to the question of approximability, but it may be useful anyway.
Andrew Ryzhikov
CC BY-SA 3.0
2015-11-07T22:32:49.753Z
@vble Regarding the second result, NP-hardness of recognition of this class is not a obstacle for the idea that I described. A characterization may be non-constructive, but imply, for example, that squares of all graphs are a subclass of some class with easy approximation of maximum independent set. Anyway, thank you for the reference!
Andrew Ryzhikov
CC BY-SA 3.0
2015-11-08T22:01:15.280Z
The fact (folklore?) can be seen as follows: Given $H$, $G$ is obtained from $H$ by subdividing each edge by a new vertex and joining every two new vertices by an edge. Then $H$ is an induced subgraph of $G^2$. Note that $G$ is even a split graph.
vb le
CC BY-SA 3.0
2015-11-09T20:15:27.133Z
Are you interested in restricted class of graphs? e.g it seems that the problem has PTAS in nowhere dense graphs.
Saeed
CC BY-SA 3.0
2015-12-27T00:15:59.787Z
@Saeed I suppose that now I am interested in restricted classes of graphs, because I have found the answer to the general question.
Andrew Ryzhikov
<graph-theory><approximation-algorithms><approximation-hardness>
Approximation algorithms for the maximum $2$-independence set problem
Andrew Ryzhikov
# Approximation algorithms for the maximum $2$-independence set problem

(Asked by: username_0 on 2015-11-07)

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.

**Tags:** graph-theory, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: Since *every* graph is (isomorphic to) an induced subgraph of the square  of some graph, the class $\mathcal{G}^2$ of squares of *all* graphs $G$ gives no hope in studying Max $2$-independece  set in *arbitrary* graphs $G$, I think. By the way, there exists no good characterization for $\mathcal{G}^2$ as proved by  Motwani and Sudan that recognizing if a given graph is the square of some graph is NP-complete,  see [here](http://www.sciencedirect.com/science/article/pii/0166218X94000239).  
> **username_0**: @vble could you please give me a reference for the first result you mentioned? I suppose, that this result does not give a direct answer to the question of approximability, but it may be useful anyway.  
> **username_0**: @vble Regarding the second result, NP-hardness of recognition of this class is not a obstacle for the idea that I described. A characterization may be non-constructive, but imply, for example, that squares of all graphs are a subclass of some class with easy approximation of maximum independent set. Anyway, thank you for the reference!  
> **username_1**: The fact (folklore?) can be seen as follows: Given $H$, $G$ is obtained from $H$ by subdividing each edge by a new vertex and joining every two new vertices by an edge. Then $H$ is an induced subgraph of $G^2$. Note that $G$ is even a split graph.  
> **username_2**: Are you interested in restricted class of graphs? e.g it seems that the problem has PTAS in nowhere dense graphs.  
> **username_0**: @Saeed I suppose that now I am interested in restricted classes of graphs, because I have found the answer to the general question.  

---

## 1 answers

### Answer by username_0 on 2015-12-27. Score: 2 | Accepted answer

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.


---

