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
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
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