Approximately counting independent sets of a given size in bounded-degree graphs
share
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density α_c(Δ) and provide (i) for α < α_c(Δ) randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most α n in n-vertex graphs of maximum degree Δ; and (ii) a proof that unless NP=RP, no such algorithms exist for α>α_c(Δ). The critical density is the occupancy fraction of hard core model on the clique K_Δ+1 at the uniqueness threshold on the infinite Δ-regular tree, giving α_c(Δ)∼e/1+e1/Δ as Δ→∞.
READ FULL TEXT