#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
690 - 711
MetadataShow full item record
© 2015 Elsevier Inc. 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 bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. Consequently, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.
AuthorsCai, JY; Galanis, A; Goldberg, LA; Guo, H; Jerrum, M; Štefankovič, D; Vigoda, E
- College Publications