<p>I don't have a good overview of this problem, but I can give some examples.
A simple approximation algorithm would be to find some order of the nodes and greedily select the nodes to be in the independent set if non of its previous neighbors have been selected in the independent set.</p>

<p>If the graph has degeneracy $d$ then using the degeneracy ordering will give a $d$-approximation.
hence for graphs of degeneracy $n^{1-\epsilon}$ we have a good enough approximation.</p>

<p>There is a couple of other techniques for approximations that work too, but I don't know them well. See:
<a href="http://en.wikipedia.org/wiki/Baker%27s_technique">http://en.wikipedia.org/wiki/Baker%27s_technique</a>
and
<a href="http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf">http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf</a></p>

<p>For the polynomial algorithms solving the problems exactly The link Suresh gave is the best. Which graphclasses that are more interesting is hard to say.</p>

<p>One class you wont find in that list is the complement of $k$-degenerate graphs.
Since max clique can be solved in $O(2^k n)$ on graphs of degeneracy $k$ see
<a href="http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm">http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm</a> 
especially the work of Eppstein.
Then Independent set is polynomial on G if the complement of G has degeneracy $O(\log n)$.</p>

CC BY-SA 3.0
2012-11-10T05:10:11.973Z
As Mohammad Al-Turkistany said in his answer cubic planar graphs are one of those non perfect graphs where independent set can be approximated.
All planar graphs has degeneracy at most 5, and graphs of genus k has degeneracy O(k) and independent set can hence approximated.
Martin Vatshelle
CC BY-SA 3.0
2012-11-09T19:25:18.553Z
2012-11-14T01:34:03.017Z
2012-11-14T01:34:03.017Z
Martin Vatshelle
<p>I haven't checked the  answers above, so my apologies if there is an overlap. Here is a special case where you can solve it exactly in polynomial time. If your graph G is a <a href="http://en.wikipedia.org/wiki/Line_graph" rel="nofollow">line graph</a>, then run a polynomial time <a href="http://dx.doi.org/10.1016/0020-0190%2873%2990029-X" rel="nofollow">algorithm</a> to find the root graph H, and then find a maximum matching in H. </p>

CC BY-SA 3.0
2012-11-14T01:32:50.123Z
Both line graphs and complement of line graphs are polynomial and covered by the list given by Suresh Venkat.
Martin Vatshelle
CC BY-SA 3.0
2012-11-13T19:06:02.933Z
2012-11-13T19:06:02.933Z
Babis Tsourakakis 
<p>For the class of cubic planar graphs, this paper, An approximation algorithm for the maximum independent set problem in cubic planar graphs by Elarbi Choukhmane and John Franco, gives a polynomial time approximation algorithm. The approximation factor of their algorithm is 6/7.</p>

CC BY-SA 3.0
2014-01-26T19:14:42.647Z
That was already obsolete by Baker's technique (FOCS'83) at the time it was published in 1986
David Eppstein
CC BY-SA 3.0
2012-11-09T22:12:05.310Z
2012-11-09T22:12:05.310Z
Mohammad Al-Turkistany
<p>In geometric intersection graphs, there are several interesting approximations, PTASs, and sub-exponential exact algorithms. See the Wikipedia article <a href="https://en.wikipedia.org/wiki/Maximum_disjoint_set" rel="nofollow">Maximum Disjoint Set</a> for a survey.</p>

CC BY-SA 3.0
2014-01-26T18:56:41.630Z
2014-01-26T18:56:41.630Z
Erel Segal-Halevi
<p>There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: <a href="http://www.graphclasses.org/classes/problem_Independent_set.html">see this entry</a> in the graph classes website. </p>

CC BY-SA 3.0
2012-11-09T18:36:05.937Z
That list aims exclusively for exact algorithms.  On the approximation, the major class might be the PTAS on planar graphs, bounded genus graphs, and H-minor-free graphs.
Yixin Cao
CC BY-SA 3.0
2012-11-10T02:15:25.617Z
Thanks Suresh. The list is quite comprehensive. Thanks also to Yan for the approximation results.
Arindam Pal
CC BY-SA 3.0
2012-11-14T19:16:19.273Z
the corresponding references are: Brenda S. Baker: Approximation Algorithms for NP-Complete Problems on Planar Graphs. J. ACM 41(1): 153-180 (1994); David Eppstein: Diameter and Treewidth in Minor-Closed Graph Families. Algorithmica 27(3): 275-291 (2000);  Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi: Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. FOCS 2005: 637-646. See also: http://courses.csail.mit.edu/6.889/fall11/lectures/L08.html and http://courses.csail.mit.edu/6.889/fall11/lectures/L09.html
Christian Sommer
CC BY-SA 3.0
2012-11-09T18:21:33.627Z
2012-11-09T18:21:33.627Z
Suresh Venkat
<p>We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon &gt; 0$ unless P = NP. What are some special classes of graphs for which better approximation algorithms are known?</p>

<p>What are the graphs for which polynomial-time algorithms are known? I know for perfect graphs this is known, but are there other interesting classes of graphs?</p>

CC BY-SA 3.0
2012-11-13T19:54:36.293Z
The exact (non-approximation) version of this question: http://cstheory.stackexchange.com/q/2503/109
András Salamon
<ds.algorithms><graph-theory><graph-algorithms><approximation-algorithms>
Approximation algorithms for Maximum Independent Set on special classes of graphs
Arindam Pal
# Approximation algorithms for Maximum Independent Set on special classes of graphs

(Asked by: username_0 on 2012-11-09)

We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better approximation algorithms are known?

What are the graphs for which polynomial-time algorithms are known? I know for perfect graphs this is known, but are there other interesting classes of graphs?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, approximation-algorithms

> **Comments:**
> **username_1**: The exact (non-approximation) version of this question: http://cstheory.stackexchange.com/q/2503/109  

---

## 5 answers

### Answer by username_7 on 2012-11-09. Score: 19 | Accepted answer

There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: [see this entry](http://www.graphclasses.org/classes/problem_Independent_set.html) in the graph classes website.

> **Comments:**
> **username_8**: That list aims exclusively for exact algorithms.  On the approximation, the major class might be the PTAS on planar graphs, bounded genus graphs, and H-minor-free graphs.  
> **username_0**: Thanks Suresh. The list is quite comprehensive. Thanks also to Yan for the approximation results.  
> **username_9**: the corresponding references are: Brenda S. Baker: Approximation Algorithms for NP-Complete Problems on Planar Graphs. J. ACM 41(1): 153-180 (1994); username_5: Diameter and Treewidth in Minor-Closed Graph Families. Algorithmica 27(3): 275-291 (2000);  Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi: Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. FOCS 2005: 637-646. See also: http://courses.csail.mit.edu/6.889/fall11/lectures/L08.html and http://courses.csail.mit.edu/6.889/fall11/lectures/L09.html  

---

### Answer by username_2 on 2012-11-09. Score: 12

I don't have a good overview of this problem, but I can give some examples.
A simple approximation algorithm would be to find some order of the nodes and greedily select the nodes to be in the independent set if non of its previous neighbors have been selected in the independent set.

If the graph has degeneracy $d$ then using the degeneracy ordering will give a $d$-approximation.
hence for graphs of degeneracy $n^{1-\epsilon}$ we have a good enough approximation.

There is a couple of other techniques for approximations that work too, but I don't know them well. See:
<http://en.wikipedia.org/wiki/Baker%27s_technique>
and
<http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf>

For the polynomial algorithms solving the problems exactly The link Suresh gave is the best. Which graphclasses that are more interesting is hard to say.

One class you wont find in that list is the complement of $k$-degenerate graphs.
Since max clique can be solved in $O(2^k n)$ on graphs of degeneracy $k$ see
<http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm>
especially the work of Eppstein.
Then Independent set is polynomial on G if the complement of G has degeneracy $O(\log n)$.

> **Comments:**
> **username_2**: As username_4 said in his answer cubic planar graphs are one of those non perfect graphs where independent set can be approximated. All planar graphs has degeneracy at most 5, and graphs of genus k has degeneracy O(k) and independent set can hence approximated.  

---

### Answer by username_4 on 2012-11-09. Score: 5

For the class of cubic planar graphs, this paper, An approximation algorithm for the maximum independent set problem in cubic planar graphs by Elarbi Choukhmane and John Franco, gives a polynomial time approximation algorithm. The approximation factor of their algorithm is 6/7.

> **Comments:**
> **username_5**: That was already obsolete by Baker's technique (FOCS'83) at the time it was published in 1986  

---

### Answer by username_3 on 2012-11-13. Score: 4

I haven't checked the answers above, so my apologies if there is an overlap. Here is a special case where you can solve it exactly in polynomial time. If your graph G is a [line graph](http://en.wikipedia.org/wiki/Line_graph), then run a polynomial time [algorithm](http://dx.doi.org/10.1016/0020-0190%2873%2990029-X) to find the root graph H, and then find a maximum matching in H.

> **Comments:**
> **username_2**: Both line graphs and complement of line graphs are polynomial and covered by the list given by username_7.  

---

### Answer by username_6 on 2014-01-26. Score: 3

In geometric intersection graphs, there are several interesting approximations, PTASs, and sub-exponential exact algorithms. See the Wikipedia article [Maximum Disjoint Set](https://en.wikipedia.org/wiki/Maximum_disjoint_set) for a survey.


---

