#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...
| المؤلفون الرئيسيون: | , , , , , , |
|---|---|
| التنسيق: | Journal article |
| منشور في: |
Pleiades Publishing
2015
|