Improved inapproximability results for counting independent sets in the hard-core model

DOI10.1002/rsa.20479zbMath1297.05177arXiv1105.5131OpenAlexW2105572930MaRDI QIDQ2877770

Andreas Galanis, Qi Ge, Linji Yang, Eric Vigoda, Daniel Štefanković

Publication date: 25 August 2014

Published in: Random Structures & Algorithms, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionapproximate countinghard-core model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items

Spatial mixing and the connective constant: optimal bounds, \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, A Spectral Independence View on Hard Spheres via Block Dynamics, Zeros and approximations of holant polynomials on the complex plane, Algorithms for hard-constraint point processes via discretization, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Factor models on locally tree-like graphs, Improved mixing condition on the grid for counting and sampling independent sets, Counting Constraint Satisfaction Problems., The Ising partition function: zeros and deterministic approximation, Approximation via Correlation Decay When Strong Spatial Mixing Fails, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, Counting hypergraph matchings up to uniqueness threshold, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, Approximating the partition function of planar two-state spin systems, Approximate Counting via Correlation Decay in Spin Systems, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Unnamed Item

Cites Work

• On the hardness of sampling independent sets beyond the tree threshold
• Random generation of combinatorial structures from a uniform distribution
• Loss networks
• Percolation and the hard-core lattice gas model
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Cylindrical algebraic decomposition using validated numerics
• Counting independent sets up to the tree threshold
• On Counting Independent Sets in Sparse Graphs
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• The Complexity of Enumeration and Reliability Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item