Approximating all independent sets of size k in a graph
In general, the maximum independent set problem cannot be approximated to within a constant factor in polynomial time unless $P = NP$. You can do better, however, if you restrict yourself to special graph classes. For example, in interval graphs, the maximum independent set problem can be solved in polynomial time. As another example, in planar graphs, the maximum independent set problem can be approximated to within any ratio $r &lt; 1$ in polynomial time.

There is a lot more information provided here: https://cstheory.stackexchange.com/questions/2503/maximal-classes-for-which-largest-independent-set-can-be-found-in-polynomial-tim
http://www.graphclasses.org/classes/problem_Independent_set.html

If you're interested in actual implementations, the Wikipedia page has a few references: https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Software_for_searching_maximum_independent_set