  We give a complete characterization of the two-state anti-ferromagnetic spin
systems which are of strong spatial mixing on general graphs. We show that a
two-state anti-ferromagnetic spin system is of strong spatial mixing on all
graphs of maximum degree at most $\Delta$ if and only if the system has a
unique Gibbs measure on infinite regular trees of degree up to $\Delta$, where
$\Delta$ can be either bounded or unbounded. As a consequence, there exists an
FPTAS for the partition function of a two-state anti-ferromagnetic spin system
on graphs of maximum degree at most $\Delta$ when the uniqueness condition is
satisfied on infinite regular trees of degree up to $\Delta$. In particular, an
FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all
infinite regular trees. This covers as special cases all previous algorithmic
results for two-state anti-ferromagnetic systems on general-structure graphs.
  Combining with the FPRAS for two-state ferromagnetic spin systems of
Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the hardness results of
Sly-Sun and independently of Galanis-Stefankovic-Vigoda, this gives a complete
classification, except at the phase transition boundary, of the approximability
of all two-state spin systems, on either degree-bounded families of graphs or
family of all graphs.
