Ising formulations of some graph-theoretic problems in psychological research: models and methods

It is well known that many NP-hard and NP-complete graph-theoretic problems can be formulated and solved as Ising spin models. We discuss several problems that have a particular history in mathematical psychology, most notably max-cut clustering, graph coloring, a linear ordering problem related to paired comparison ranking and directed acyclic graphs, and the problem of finding a minimum subset of points necessary to contain another point within a convex hull. New Ising spin models are presented for the latter two problems. In addition, we provide MATLAB software programs for obtaining solutions via enumeration of all spin ensembles (when computationally feasible) and simulated annealing. Although we are not advocating that the Ising spin model is the preferred approach for formulation and solution of graph-theoretic problems on conventional digital computers, it does provide a unifying framework for these problems. Moreover, recent progress in the development of quantum computing architecture has shown that Ising spin models can afford enormous improvements in algorithm efficiency when implemented on these platforms, which may ultimately lead to widespread use of the methodology in the future.