3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – vb le
    Nov 7, 2015 at 22:02
  • $\begingroup$ @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. $\endgroup$
    – Andrew Ryzhikov
    Nov 7, 2015 at 22:28
  • 2
    $\begingroup$ @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! $\endgroup$
    – Andrew Ryzhikov
    Nov 7, 2015 at 22:32
  • 3
    $\begingroup$ 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. $\endgroup$
    – vb le
    Nov 8, 2015 at 22:01
  • $\begingroup$ Are you interested in restricted class of graphs? e.g it seems that the problem has PTAS in nowhere dense graphs. $\endgroup$
    – Saeed
    Nov 9, 2015 at 20:15

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.