On the hardness of sampling independent sets beyond the tree threshold

DOI10.1007/S00440-007-0131-9zbMATH Open1165.60028arXivmath/0701471OpenAlexW2048759201MaRDI QIDQ1017883FDOQ1017883

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)

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.

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The \(\zeta(2)\) limit in the random assignment problem
• Title not available (Why is that?)
• Counting independent sets up to the tree threshold
• Polynomial-Time Approximation Algorithms for the Ising Model
• Title not available (Why is that?)
• The Parisi formula
• Title not available (Why is that?)
• On Counting Independent Sets in Sparse Graphs
• Glauber dynamics on trees and hyperbolic graphs
• Title not available (Why is that?)
• Design of capacity-approaching irregular low-density parity-check codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Markov Chains for Independent Sets
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on the Glauber dynamics for sampling independent sets
• A second threshold for the hard‐core model on a Bethe lattice

Cited In (39)

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

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)