Title: On the complexity of counting and deciding existence of
Satisfying Spin-Assignments in Triangulations

Authors: Andrea Jimenez (University of Chile) and Marcos Kiwi
(University of Chile)

Abstract: Satisfying spin-assignments in triangulations are states of
minimum energy of the anti-ferromagnetic Ising model on triangulations,
which correspond (via geometric duality) to perfect matchings in cubic
bridgeless graphs. In this work we show that it is NP-complete to decide
whether or not a triangulation admits a satisfying spin-assignment, and
that it is #P-complete to determine the number of such assignments. Both
results are derived via an elaborate (and atypical) reduction that maps
Boolean formulas in 3-conjunctive normal form into a triangulation of a
orientable closed surface.