#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #Sat to approximate. We study #BIS in the general framework of two-state spin systems on bipart...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Journal article |
| Published: |
Pleiades Publishing
2015
|