2021/01/06 by Heinrich, Marc, Müller, Haiko
#05C30 05C85 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #G.2.2
paper · doi:10.48550/arxiv.2101.01997
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 .