Abstract
We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Δ. More generally, for an input graph G = (V,E) and an activity λ > 0, we are interested in the quantity Z G (λ) defined as the sum over independent sets I weighted as w(I) = λ |I|. In statistical physics, Z G (λ) is the partition function for the hard-core model, which is an idealized model of a gas where the particles have non-negibile size. Recently, an interesting phase transition was shown to occur for the complexity of approximating the partition function. Weitz showed an FPAS for the partition function for any graph of maximum degree Δ when Δ is constant and \(\lambda<\lambda_c(\mathbb{T}_\Delta):=(\Delta-1)^{\Delta-1}/(\Delta-2)^\Delta\). The quantity \(\lambda_c(\mathbb{T}_\Delta)\) is the critical point for the so-called uniqueness threshold on the infinite, regular tree of degree Δ. On the other side, Sly proved that there does not exist efficient (randomized) approximation algorithms for \(\lambda_c(\mathbb{T}_\Delta)<\lambda<\lambda_c(\mathbb{T}_\Delta)+\varepsilon(\Delta)\), unless NP=RP, for some function ε(Δ) > 0. We remove the upper bound in the assumptions of Sly’s result for Δ ≠ 4,5, that is, we show that there does not exist efficient randomized approximation algorithms for all \(\lambda>\lambda_c(\mathbb{T}_\Delta)\) for Δ = 3 and Δ ≥ 6. Sly’s inapproximability result uses a clever reduction, combined with a second-moment analysis of Mossel, Weitz and Wormald which prove torpid mixing of the Glauber dynamics for sampling from the associated Gibbs distribution on almost every regular graph of degree Δ for the same range of λ as in Sly’s result. We extend Sly’s result by improving upon the technical work of Mossel et al., via a more detailed analysis of independent sets in random regular graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
van den Berg, J., Steif, J.E.: Percolation and the hard-core lattice gas model. Stochastic Processes and their Applications 49(2), 179–197 (1994)
Dyer, M., Frieze, A.M., Jerrum, M.: On counting independent sets in sparse graphs. SIAM J. Comput. 31(5), 1527–1541 (2002)
Galanis, A., Ge, Q., Štefankovič, D., Vigoda, E., Yang, L.: Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model (2011) Preprint available from the arXiv at, http://arxiv.org/abs/1105.5131
Gaunt, D.S., Fisher, M.E.: Hard-Sphere Lattice Gases. I. Plane-Square Lattice. Journal of Chemical Physics 43(8), 2840–2863 (1965)
Greenhill, C.: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity 9(1), 52–72 (2000)
Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution distribution. Theoretical Computer Science 43(2-3), 169–186 (1986)
Kelly, F.P.: Loss Networks. Annals of Applied Probability 1(3), 319–378 (1991)
Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009)
Molloy, M., Robalewska, H., Robinson, R.W., Wormald, N.C.: 1-factorizations of random regular graphs. Random Structures and Algorithms 10(3), 305–321 (1997)
Mossel, E., Weitz, D., Wormald, N.: On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields 143(3-4), 401–439 (2009)
Sly, A.: Computational Transition at the Uniqueness Threshold. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287-296 (2010), Full version available from the arXiv at, http://arxiv.org/abs/1005.5584
Štefankovič, D., Vempala, S., Vigoda, E.: Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. Journal of the ACM 56(3), 1–36 (2009)
Strzebonski, A.W.: Cylindrical algebraic decomposition using validated numerics. J. Symb. Comput. 41(9), 1021–1038 (2006)
Tarski, A.: RAND Corporation, Santa Monica, Calif. RAND Corporation, Santa Monica (1948)
Valiant, L.G.: The Complexity of Enumeration and Reliability Problems. SIAM J. Computing 8(3), 410–421 (1979)
Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 140–149 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Galanis, A., Ge, Q., Štefankovič, D., Vigoda, E., Yang, L. (2011). Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2011 2011. Lecture Notes in Computer Science, vol 6845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22935-0_48
Download citation
DOI: https://doi.org/10.1007/978-3-642-22935-0_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22934-3
Online ISBN: 978-3-642-22935-0
eBook Packages: Computer ScienceComputer Science (R0)