Counting independent sets in graphs with bounded bipartite pathwidth. Issue 2 (10th March 2021)

• Record Type: Journal Article
• Authors: Dyer, Martin; Greenhill, Catherine; Müller, Haiko
• Is Part Of: Random structures & algorithms. Volume 59:Issue 2(2021)
• Page Start: 204
• Page End: 237
• Publication Date: 2021-03-10
• Subjects: approximate counting -- independent sets -- pathwidth; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21003
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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.