Algorithms for #BIS-hard problems on expander graphs

DOI10.1137/1.9781611975482.135MaRDI QIDQ5236322zbMATH OpenOpenAlexFDO

Authors Matthew Jenssen, Peter Keevash, Will Perkins

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.04804

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) $Delta$-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite $Delta$-regular tree. We also find efficient counting and sampling algorithms for proper $q$-colorings of random $Delta$-regular bipartite graphs when $q$ is sufficiently small as a function of $Delta$.

Recommendations

• Algorithms for \#BIS-hard problems on expander graphs
• Algorithms for classes of graphs with bounded expansion
• Algorithms and experiments for parameterized approaches to hard graph problems
• Theoretical Computer Science
• Exact algorithms for difficult graph problems
• On the complexity of some problems related to graph extensions
• Exact exponential-time algorithms for finding bicliques
• On the parameterized complexity of computing graph bisections
• Graph Drawing
• Expander graphs and their applications

Cited in

(22)

• Exact exponential-time algorithms for finding bicliques
• Polymer dynamics via cliques: new conditions for approximations
• An FPTAS for the hardcore model on random regular bipartite graphs
• Algorithmic Pirogov-Sinai theory
• Faster exponential-time algorithms for approximately counting independent sets
• Algorithms for \#BIS-hard problems on expander graphs
• Fast algorithms for general spin systems on bipartite expanders
• Fast algorithms for general spin systems on bipartite expanders
• Independent sets in the hypercube revisited
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Weighted counting of solutions to sparse systems of equations
• Efficient algorithms for approximating quantum partition functions
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• scientific article; zbMATH DE number 7650108 (Why is no real title available?)
• scientific article; zbMATH DE number 7650121 (Why is no real title available?)
• Fast algorithms at low temperatures via Markov chains†
• Approximately counting independent sets in bipartite graphs via graph containers
• Expanders via local edge flips in quasilinear time
• Efficient algorithms for the Potts model on small-set expanders
• Algorithms for the ferromagnetic Potts model on expanders
• Correlation decay and partition function zeros: algorithms and phase transitions
• A spectral independence view on hard spheres via block dynamics

This page was built for publication: Algorithms for #BIS-hard problems on expander graphs

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