Cai, JinYi ;
Galanis, Andreas ;
Goldberg, Leslie Ann ;
Guo, Heng ;
Jerrum, Mark ;
Stefankovic, Daniel ;
Vigoda, Eric
#BISHardness for 2Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
Abstract
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 twostate spin systems in bipartite graphs. Such a system is parameterized by three numbers (beta,gamma,lambda), where beta (respectively gamma) represents the weight of an edge (or "interaction strength") whose endpoints are of the same 0 (respectively 1) spin, and lambda is the weight of a 1 vertex, also known as an "external field". By convention, the edge weight with unequal 0/1 end points and the vertex weight with spin 0 are both normalized to 1. The partition function of the special case beta=1, gamma=0, and lambda=1 counts the number of independent sets. We define two notions, nearlyindependent phasecorrelated spins and symmetry breaking. We prove that it is #BIShard to approximate the partition function of any twospin system on bipartite graphs supporting these two notions.
As a consequence, we show that #BIS on graphs of degree at most 6 is as hard to approximate as #BIS~without degree bound. The degree bound 6 is the best possible as Weitz presented an FPTAS to count independent sets on graphs of maximum degree 5. This result extends to the hardcore model and to other antiferromagnetic twospin models. In particular, for all antiferromagnetic twospin systems, namely those satisfying beta*gamma<1, we prove that when the infinite (Delta1)ary tree lies in the nonuniqueness region then it is #BIShard to approximate the partition function on bipartite graphs of maximum degree Delta, except for the case beta=gamma and lambda=1. The exceptional case is precisely the antiferromagnetic Ising model without an external field, and we show that it has an FPRAS on bipartite graphs. Our inapproximability results match the approximability results of Li et al., who presented an FPTAS for general graphs of maximum degree Delta when the parameters lie in the uniqueness region.
BibTeX  Entry
@InProceedings{cai_et_al:LIPIcs:2014:4723,
author = {JinYi Cai and Andreas Galanis and Leslie Ann Goldberg and Heng Guo and Mark Jerrum and Daniel Stefankovic and Eric Vigoda},
title = {{#BISHardness for 2Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {582595},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4723},
URN = {urn:nbn:de:0030drops47235},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.582},
annote = {Keywords: Spin systems, approximate counting, complexity, #BIShardness, phase transition}
}
04.09.2014
Keywords: 

Spin systems, approximate counting, complexity, #BIShardness, phase transition 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Issue date: 

2014 
Date of publication: 

04.09.2014 