Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model

Andreas Galanis, Qi Ge, Daniel Stefankovic +2

We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Delta. More generally, for an input graph G=(V,E) and…