Counting independent sets in graphs with bounded bipartite pathwidth.

We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The class is determined by boundedness of a new graph parameter called bipartite pathwidth. This result, which we prove for the more general hardcore distribution with fugacity λ, can be viewed as a strong generalization of Jerrum and Sinclair's work on approximately counting matchings, that is, independent sets in line graphs. The class of graphs with bounded bipartite pathwidth includes claw-free graphs, which generalize line graphs. We consider two further generalizations of claw-free graphs and prove that these classes have bounded bipartite pathwidth. We also show how to extend all our results to polynomially bounded vertex weights. [ABSTRACT FROM AUTHOR]