Document Open Access Logo

Inapproximability of the Independent Set Polynomial Below the Shearer Threshold

Authors Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2017.28.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • approximate counting
  • independent set polynomial
  • Shearer threshold

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the problem of approximately evaluating the independent set polynomial of bounded-degree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hard-core model with activity lambda on graphs G of max degree D. For lambda>0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at lambda_c(D)=(D-1)^(D-1)/(D-2)^D, which coincides with the tree uniqueness phase transition from statistical physics. 

For lambda<0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Shearer identified the threshold lambda*(D)=(D-1)^(D-1)/D^D as the maximum value p such that every family of events with failure probability at most p and whose dependency graph has max degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey et al. have independently designed FPTASes for approximating the partition function whenever |lambda|<lambda*(D). 

Our main result establishes for the first time a computational transition at the Shearer threshold. We show that for all D>=3, for all lambda<-lambda*(D), it is NP-hard to approximate the partition function on graphs of maximum degree D, even within an exponential factor. Thus, our result, combined with the FPTASes for lambda>-lambda*(D), establishes a phase transition for negative activities. In fact, we now have the following picture for the problem of approximating the partition function with activity lambda on graphs G of max degree D. 
1. For -lambda*(D)<lambda<lambda_c(D), the problem admits an FPTAS. 
2. For lambda<-lambda*(D) or lambda>lambda_c(D), the problem is NP-hard. 
Rather than the tree uniqueness threshold of the positive case, the phase transition for negative activities corresponds to the existence of zeros for the partition function of the tree below -lambda*(D).

Cite As Get BibTex

Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic. Inapproximability of the Independent Set Polynomial Below the Shearer Threshold. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.28

Author Details

Andreas Galanis
Leslie Ann Goldberg
Daniel Stefankovic

References

  1. Dimitris Achlioptas and Fotis Iliopoulos. Random walks that find perfect objects and the Lovász Local Lemma. J. ACM, 63(3):Article No. 22, July 2016. Google Scholar
  2. József Beck. An algorithmic approach to the Lovász Local Lemma. I. Random Structures &Algorithms, 2(4):343-365, 1991. Google Scholar
  3. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combinatorics, Probability and Computing, 25(4):500-559, 2016. Google Scholar
  4. Leslie A. Goldberg and Mark Jerrum. Inapproximability of the Tutte polynomial of a planar graph. Computational Complexity, 21(4):605-642, 2012. Google Scholar
  5. Leslie A. Goldberg and Mark Jerrum. The complexity of computing the sign of the Tutte polynomial. SIAM Journal on Computing, 43(6):1921-1952, 2014. Google Scholar
  6. Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the Lovász Local lemma. CoRR, abs/1611.01647, 2016. Google Scholar
  7. David G. Harris and Aravind Srinivasan. A constructive algorithm for the Lovász Local Lemma on permutations. In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 907-925, Philadelphia, PA, USA, 2014. Society for Industrial and Applied Mathematics. Google Scholar
  8. Nicholas J. A. Harvey, Piyush Srivastava, and Jan Vondrák. Computing the independence polynomial in Shearer’s region for the LLL. CoRR, abs/1608.02282, 2016. Google Scholar
  9. Nicholas J. A. Harvey and Jan Vondrák. An algorithmic proof of the Lovász Local Lemma via resampling oracles. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS'15, pages 1327-1346, Washington, DC, USA, 2015. IEEE Computer Society. Google Scholar
  10. Kashyap B. R. Kolipaka and Mario Szegedy. Moser and Tardos meet Lovász. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC'11, pages 235-244, New York, NY, USA, 2011. ACM. Google Scholar
  11. Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 67-84, 2013. Google Scholar
  12. Ankur Moitra. Approximate counting, the Lovász Local lemma and inference in graphical models. CoRR, abs/1610.04317, 2016. Google Scholar
  13. Robin A. Moser. A constructive proof of the Lovász Local Lemma. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC'09, pages 343-350, New York, NY, USA, 2009. Google Scholar
  14. Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász Local lemma. J. ACM, 57(2):Article No. 11, 2010. Google Scholar
  15. Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. CoRR, abs/1607.01167, 2016. Google Scholar
  16. Alexander D. Scott and Alan D. Sokal. The repulsive lattice gas, the independent-set polynomial, and the Lovász Local Lemma. J. Stat. Phys., 118(5):1151-1261, 2005. Google Scholar
  17. J. B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241-245, 1985. Google Scholar
  18. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. J. Stat. Phys., 155(4):666-686, 2014. Google Scholar
  19. Allan Sly. Computational transition at the uniqueness threshold. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS'10, pages 287-296, Washington, DC, USA, 2010. IEEE Computer Society. Google Scholar
  20. Allan Sly and Nike Sun. Counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383-2416, 11 2014. Google Scholar
  21. Piyush Srivastava. Approximating the hard core partition function with negative activities. Manuscript, available at http://www.its.caltech.edu/~piyushs/, April 2015.
  22. Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC'06, pages 140-149, New York, NY, USA, 2006. ACM. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact