← All problems

The computational hardness threshold conjecture for weighted independent sets

19 years old · traced to

Let d≥3d\geq 3 be the maximum degree, let ℓ\ell be the activity, and let ℓc(d)=(d−1)d−1/(d−2)d\ell_c(d)=(d-1)^{d-1}/(d-2)^d be the critical activity for decay of correlations on the infinite dd-regular tree. Consider the weighted sum of independent sets, with each independent set II having weight ℓ∣I∣\ell^{|I|}. Computational hardness threshold conjecture. For every d>3d>3 and all ℓ>ℓc(d)\ell>\ell_c(d), unless RP=NPRP=NP, there does not exist a fully polynomial approximation scheme for counting weighted independent sets in graphs of maximum degree dd with activity ℓ\ell.

References

Status

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

Never refreshed

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.