Approximating all independent sets of size k in a graph Given an undirected graph, I need an algorithm that outputs all the independent sets of size >= k (constant) in the graph. I know the problem is NPC, and I do not want to use the exponential brute-force solution. What I am looking for is to hear about the best solutions currently known to this problem. If someone can refer me to some known polynomial approximation algorithms that achieve good results, that would be very helpful.
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