<p>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)$.</p>

<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.9195" rel="nofollow">this paper by Guibas, Hershberger, Mitchell and Snoeyink</a>. Thus, it appears that there may be no interesting polynomial-time generalization of the planar Ising model algorithm.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-26T17:55:31.177Z
I wonder if it's then a candidate for problems not known to be in P or NPC: http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc
Suresh Venkat
CC BY-SA 2.5
2010-12-26T17:57:13.370Z
@Suresh: that was quick. I was editing my answer to suggest the same thing myself while you were adding the comment.
Peter Shor 
CC BY-SA 2.5
2010-12-26T18:04:20.980Z
oh sorry. didn't realize that.
Suresh Venkat
CC BY-SA 2.5
2010-12-26T19:25:53.493Z
No need to apologize. You couldn't know I had the same idea a few seconds after I hit the post button.
Peter Shor 
CC BY-SA 2.5
2011-02-25T02:39:09.690Z
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 
CC BY-SA 2.5
2010-12-26T17:51:55.297Z
2011-02-25T22:27:49.720Z
2011-02-25T22:27:49.720Z
Peter Shor 
<p>Kastelyn in the 1960's continuing Onsanger's work on the <a href="http://en.wikipedia.org/wiki/Ising_model" rel="nofollow">Ising model</a>, found combinatorial solutions to the 2 dimensional planar Ising model. This was for undirected graphs. </p>

<blockquote>
  <p>Has a similar algorithm been found for planar <em>directed</em> graphs?</p>
</blockquote>

<p>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:</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-22T14:29:06.527Z
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 
CC BY-SA 2.5
2010-12-23T19:57:06.030Z
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
CC BY-SA 2.5
2010-12-24T00:28:13.240Z
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 
<ds.algorithms><planar-graphs>
Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs
Zelah 02
# Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs

(Asked by: username_0 on 2010-12-22)

Kastelyn in the 1960's continuing Onsanger's work on the [Ising model](http://en.wikipedia.org/wiki/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.

**Tags:** ds.algorithms, planar-graphs

> **Comments:**
> **username_1**: Maybe you could say exactly what the Ising model is for directed graphs. I am only familiar with the Ising model for undirected graphs.  
> **username_2**: 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.  
> **username_1**: 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$?  

---

## 1 answers

### Answer by username_1 on 2010-12-26. Score: 6 | Accepted 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.9195). 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.

> **Comments:**
> **username_3**: I wonder if it's then a candidate for problems not known to be in P or NPC: http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc  
> **username_1**: @Suresh: that was quick. I was editing my answer to suggest the same thing myself while you were adding the comment.  
> **username_3**: oh sorry. didn't realize that.  
> **username_1**: No need to apologize. You couldn't know I had the same idea a few seconds after I hit the post button.  
> **username_1**: 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.  

---

