Finding a Maximum Independent Set
Robert Endre Tarjan, Anthony E. Trojanowski · SIAM Journal on Computing · 1977
We present an algorithm which finds a maximum independent set in an n-vertex graph in $O(2^{n/3})$ time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.