Physicists use a model called an Ising spin glass to study magnetic materials. We have a graph G=(V,E) and a function J:EZ, where J(u,v) is the interaction strength of edge {u,v}E. A state is a function s:V{1,+1}1. The energy of a state s is H(s)={u,v}EEJ(u,v)s(u)s(v).2Anedge{u,v} is called ferromagnetic if J(u,v)>0, and antiferromagneticifJ(u,v)