# Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs

Kastelyn in the 1960's continuing Onsanger's work on the Ising model, found combinatorial solutions to the 2 dimensional planar Ising model. This was for undirected graphs.

Has a similar algorithm been found for planar directed graphs?

To clarify what I mean, although there are several different ways one could generalise the planar Ising model to directed graphs, I have in the mind the following:

The 2-local term in the standard Ising model is the symmetric matrix $J_{ij}$. The directed graph would be represented by unsymmetric matrix $J_{ij}$! So the sum over the partition function would be unsymmetrical. I hope this helps.

• Maybe you could say exactly what the Ising model is for directed graphs. I am only familiar with the Ising model for undirected graphs. – Peter Shor Dec 22 '10 at 14:29
• I think many theoretical computer scientists have heard of the Ising model but probably do not remember precisely what it is. It would help if you defined it. – Warren Schudy Dec 23 '10 at 19:57
• I still don't understand the Ising model for directed graphs. I don't believe this is standard terminology. Please provide some more details. Is there a motivation for your question? According to Wikipedia, the two-local term for the standard Ising model is $-J_{ij}S_iS_j$. (Is this what you mean when you say $J_{ij}$ is the two-local term?) How does an asymmetric $J_{ij}$ make any difference when you plug this term into $-J_{ij}S_iS_j$? – Peter Shor Dec 24 '10 at 0:28

## 1 Answer

If you take the standard Ising model: min $E= -\sum_{i \neq j}J_{ij}S_iS_j$, where $S_k =\pm 1$, and replace $J_{ij}$ with a non-symmetric matrix, it remains the standard Ising model. This is because you can rewrite the terms $- J_{ij}S_i S_j -J_{ji}S_j S_i = - \frac{J_{ij} + J_{ji}}{2} (S_iS_j + S_j S_i)$.

A more interesting asymmetric generalization of the planar Ising model is planar MAX 2-SAT (the problem planar MIN 2-SAT is equivalent). This is the problem MAX 2-SAT where the clauses are on the edges of a planar graph. Planar MAX 2-SAT is NP-hard: look at this paper by Guibas, Hershberger, Mitchell and Snoeyink. Thus, it appears that there may be no interesting polynomial-time generalization of the planar Ising model algorithm.

I should note that for planar MAX 2-SAT to be a generalization of the planar Ising model, you need to restrict the Ising model to polynomial-size integers $J_{ij}$. The obvious reduction also requires a planar multigraph, but there's an easy proof that planar MAX 2-SAT on a graph and on a multigraph are equivalent problems.

• I wonder if it's then a candidate for problems not known to be in P or NPC: cstheory.stackexchange.com/questions/79/… – Suresh Venkat Dec 26 '10 at 17:55
• @Suresh: that was quick. I was editing my answer to suggest the same thing myself while you were adding the comment. – Peter Shor Dec 26 '10 at 17:57
• oh sorry. didn't realize that. – Suresh Venkat Dec 26 '10 at 18:04
• No need to apologize. You couldn't know I had the same idea a few seconds after I hit the post button. – Peter Shor Dec 26 '10 at 19:25
• And it turns out that planar MAX 2-SAT was proved NP-complete in 1991, as a lemma in another paper, and it has remained an obscure result since. See the update to my answer. – Peter Shor Feb 25 '11 at 2:39