counting independent sets
The problem can be restated as a #2SAT. See 

http://en.wikipedia.org/wiki/2-satisfiability 

under the "Counting the number of satisfying assignments" section for some references to the currently best exact counting algorithms.