The computational hardness threshold conjecture for weighted independent sets
Let be the maximum degree, let be the activity, and let be the critical activity for decay of correlations on the infinite -regular tree. Consider the weighted sum of independent sets, with each independent set having weight . Computational hardness threshold conjecture. For every and all , unless , there does not exist a fully polynomial approximation scheme for counting weighted independent sets in graphs of maximum degree with activity .
References
Status
- Solved: Andreas Galanis, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Hardness of approximately counting in the hard-core model (Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS 2016), 2016) https://www.cs.rochester.edu/~stefanko/Publications-new/C26.pdf
Source: Elchanan Mossel, Dror Weitz and Nicholas Wormald, “On the hardness of sampling independent sets beyond the tree threshold”, arXiv:math/0701471 (2007).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.