On the hardness of sampling independent sets beyond the tree threshold

DOI10.1007/S00440-007-0131-9MaRDI QIDQ1017883zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Dror Weitz, Nicholas Wormald

Publication date 13 May 2009

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25)

Abstract: We consider local Markov chain Monte-Carlo algorithms for sampling from the weighted distribution of independent sets with activity $l$, where the weight of an independent set $I$ is $l^{|I|}$. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree $d$ and $l<l_c(d)$, where $l_c(d)$ is the critical activity for uniqueness of the Gibbs measure (i.e., for decay of correlations with distance in the weighted distribution over independent sets) on the $d$-regular infinite tree. We show that for $dgeq3$, $l$ just above $l_c(d)$ with high probability over $d$-regular bipartite graphs, any local Markov chain Monte-Carlo algorithm takes exponential time before getting close to the stationary distribution. Our results provide a rigorous justification for ``replica method heuristics. These heuristics were invented in theoretical physics and are used in order to derive predictions on Gibbs measures on random graphs in terms of Gibbs measures on trees. We conjecture that $l_c$ is in fact the exact threshold for this computational problem, i.e., that for $l>l_c$ it is NP-hard to approximate the above weighted sum overindependent sets to within a factor polynomial in the size of the graph.

Recommendations

• Counting independent sets up to the tree threshold
• Fast convergence of the Glauber dynamics for sampling independent sets

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 5764879 (Why is no real title available?)
• scientific article; zbMATH DE number 3951995 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1033851 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1559584 (Why is no real title available?)
• scientific article; zbMATH DE number 1775410 (Why is no real title available?)
• scientific article; zbMATH DE number 6469177 (Why is no real title available?)
• A note on the Glauber dynamics for sampling independent sets
• A second threshold for the hard‐core model on a Bethe lattice
• Counting independent sets up to the tree threshold
• Design of capacity-approaching irregular low-density parity-check codes
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Glauber dynamics on trees and hyperbolic graphs
• On Counting Independent Sets in Sparse Graphs
• On Markov Chains for Independent Sets
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Parisi formula
• The \(\zeta(2)\) limit in the random assignment problem

Cited in

(37)

• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
• Bethe states of random factor graphs
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• Branching process approach for 2-SAT thresholds
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Fast algorithms at low temperatures via Markov chains†
• Approximate counting via correlation decay in spin systems
• A spectral independence view on hard spheres via block dynamics
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• scientific article; zbMATH DE number 7650108 (Why is no real title available?)
• Factor models on locally tree-like graphs
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Glauber dynamics for Ising model on convergent dense graph sequences
• Phase transitions in sampling algorithms and the underlying random structures
• Counting constraint satisfaction problems
• Phase transitions in discrete structures
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Tunneling of the hard-core model on finite triangular lattices
• Gibbs measures and phase transitions on sparse random graphs
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Harnessing the Bethe free energy
• Algorithms for \#BIS-hard problems on expander graphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Counting independent sets up to the tree threshold
• Mixing of Markov chains for independent sets on chordal graphs with bounded separators
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Counting hypergraph matchings up to uniqueness threshold
• Polymer dynamics via cliques: new conditions for approximations
• On computing minimal independent support and its applications to sampling and counting
• An FPTAS for the hardcore model on random regular bipartite graphs
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs

This page was built for publication: On the hardness of sampling independent sets beyond the tree threshold

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