Counting independent sets in graphs with bounded bipartite pathwidth

Martin Dyer, Catherine Greenhill, Haiko Müller

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 c…