Counting independent sets in strongly orderable graphs

Abstract

We consider the problem of devising algorithms to count exactly the number of independent sets of a graph G . We show that there is a polynomial time algorithm for this problem when G is restricted to the class of strongly orderable graphs, a superclass of chordal bipartite graphs. We also show that such an algorithm exists for graphs of bounded clique-width. Our results extends to a more general setting of counting independent sets in a weighted graph and can be used to count the number of independent sets of any given size k .