Counting independent sets in graphs with bounded bipartite pathwidth

DOI10.1007/978-3-030-30786-8_23arXiv1812.03195MaRDI QIDQ6310891

Catherine Greenhill, Martin Dyer, Haiko Müller

Publication date: 7 December 2018

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 $lambda$, can be viewed as a strong generalisation 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 generalise line graphs. We consider two further generalisations 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.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)

This page was built for publication: Counting independent sets in graphs with bounded bipartite pathwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6310891)