We consider the problem of computing the Bethe partition function of an arbitrary pairwise binary graphical model.  We show that, in many cases of interest, the problem can be solved exactly in polynomial time or approximated with a polynomial time approximation scheme.  In the process, we completely characterize the class of strictly positive graphical models with no frustrated cycles in terms of graph covers.