<p>The counterexamples you give are not correct. I suspect your bug is this: when doing the sums over edges in (or not in) $E_1$ and $E_2$, you need to consider both orderings of each pair. </p>

<p>Consider your first false positive. One of the mismatched edges corresponds to (the lack of) $(2,4)$ in $G_1$, which maps to $(3,1)$ in $G_2$ (which is present). This makes the third term in the sum non-zero: consider $(i,j)$=$(2,4)$ and $(u,v)$=$(3,1)$; $x_{3,2}x_{1,4}$ is non-zero. If you only consider the edge pairs $(u,v)$ where $u&lt;v$, you miss counting these non-zero terms and get the incorrect zero result.</p>

CC BY-SA 3.0
2014-07-24T16:04:05.343Z
following your suggestion, I was able to fix my objective function.
Omar Shehab
CC BY-SA 3.0
2014-07-24T19:56:23.713Z
I also got correct result for a non-isomorphic pair following your suggestion.
Omar Shehab
CC BY-SA 3.0
2014-07-24T20:14:43.493Z
Glad to have helped!
William Whistler
CC BY-SA 3.0
2014-07-24T08:11:07.860Z
2014-07-24T08:11:07.860Z
William Whistler
<p>I am going to through <a href="http://journal.frontiersin.org/Journal/10.3389/fphy.2014.00005/abstract" rel="nofollow noreferrer">Ising formulations of many NP problems</a> by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two gaphs, $G_1$ and $G_2$, the Ising Hamiltonian, $H$ is,</p>

<p>$$
H = A \sum_v \left(1 - \sum_i x_{v,i}\right)^2 + A \sum_i \left(1 - \sum_v x_{v,i}\right)^2 \\
+ B\sum_{ij\not\in E_1}\sum_{uv \in E_2} x_{u,i} x_{v,j} + B \sum_{ij \in E_1}\sum_{uv \not\in E_2} x_{u,i} x_{v,j}
$$</p>

<p>Here, $|G_1|=|G_2|$ and the binary variable $x_{v,i}$ is $1$ when if vertex $v$ in $G_2$ is mapped to vertex $i$ of $G_1$. For an isomorphic pair, $H = 0$.</p>

<p><strong>My questions:</strong></p>

<ol>
<li>Is there any rigorous proof that this model is correct?</li>
<li>I understand that the classical computational complexity of the graph isomorphism problem is not known but it is conjectured to be NP-intermediate. On the other hand the classical computational complexity of the Ising model is well understood. So, if the graph isomorphism problem can be reduced to an Ising model in polynomial time, shouldn't be it's complexity same as the Ising model problem?</li>
<li>When I code it up using Mathematica (assuming $A = B = 1$) for the following two isomorphic graph pairs, I am getting false positives.</li>
</ol>

<p>The graphs are: </p>

<p><img src="https://i.sstatic.net/S8lrJ.png" alt="enter image description here"> and <img src="https://i.sstatic.net/ViVWf.png" alt="enter image description here">.</p>

<p>For this pair of graphs, I get the following configurations which are correct isomorphisms and for them $H=0$. They are: </p>

<ol>
<li>$x_{1,1}, x_{2,2}, x_{4,3}, x_{3,4}$</li>
<li>$x_{4,1}, x_{3,2}, x_{1,3}, x_{2,4}$</li>
<li>$x_{1,1}, x_{3,2}, x_{4,3}, x_{2,4}$</li>
<li>$x_{4,1}, x_{2,2}, x_{1,3}, x_{3,4}$ </li>
</ol>

<p>But when I evaluate the Ising formulation with all possible inputs using Mathematica, I get five more false positives along with these four. They are:</p>

<ol>
<li>$x_{1,4}, x_{2,3}, x_{3,2}, x_{4,1}$</li>
<li>$x_{1,4}, x_{2,2}, x_{3,1}, x_{4,3}$</li>
<li>$x_{1,3}, x_{2,4}, x_{3,1}, x_{4,2}$</li>
<li>$x_{1,1}, x_{2,4}, x_{3,3}, x_{4,2}$</li>
<li>$x_{1,4}, x_{2,3}, x_{3,1}, x_{4,2}$</li>
</ol>

<p>What am I missing?</p>

CC BY-SA 3.0
2014-07-24T00:17:51.337Z
Isn't the complexity of the Ising model known, but known to be hard (e.g. NP-hard)? If it's hard, then the fact that GI reduces to something, say, NP-hard is not new or surprising and doesn't tell you anything new about the complexity of GI. (Also, just a small note: "not known and hence NP-intermediate" -> "not known and *conjecturally* NP-intermediate")
Joshua Grochow
CC BY-SA 3.0
2014-07-24T08:37:42.677Z
@JoshuaGrochow, the Ising model is NP-complete - a result of Sorin Istrail.
Omar Shehab
CC BY-SA 3.0
2014-07-24T16:05:15.260Z
@JoshuaGrochow As the Ising model is known to be NP-Complete, any problem which can be reduced to Ising model in polynomial time should also be NP-Complete. Isn't it what is happening here?
Omar Shehab
CC BY-SA 3.0
2014-07-24T18:05:44.310Z
Just the opposite: a problem L can be reduced to the Ising model if and only if L is in NP. If the reduction went the *opposite way* (the Ising model reduces to Graph Isomorphism), then that would say that GI is NP-complete (and therefore that PH collapses).
Joshua Grochow
<reductions><graph-isomorphism><statistical-physics>
Proof of an Ising model representation of graph isomorphism problem
Omar Shehab
# Proof of an Ising model representation of graph isomorphism problem

(Asked by: username_0 on 2014-07-23)

I am going to through [Ising formulations of many NP problems](http://journal.frontiersin.org/Journal/10.3389/fphy.2014.00005/abstract) by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two gaphs, $G\_1$ and $G\_2$, the Ising Hamiltonian, $H$ is,

$$
H = A \sum\_v \left(1 - \sum\_i x\_{v,i}\right)^2 + A \sum\_i \left(1 - \sum\_v x\_{v,i}\right)^2 \\
+ B\sum\_{ij\not\in E\_1}\sum\_{uv \in E\_2} x\_{u,i} x\_{v,j} + B \sum\_{ij \in E\_1}\sum\_{uv \not\in E\_2} x\_{u,i} x\_{v,j}
$$

Here, $|G\_1|=|G\_2|$ and the binary variable $x\_{v,i}$ is $1$ when if vertex $v$ in $G\_2$ is mapped to vertex $i$ of $G\_1$. For an isomorphic pair, $H = 0$.

**My questions:**

1. Is there any rigorous proof that this model is correct?
2. I understand that the classical computational complexity of the graph isomorphism problem is not known but it is conjectured to be NP-intermediate. On the other hand the classical computational complexity of the Ising model is well understood. So, if the graph isomorphism problem can be reduced to an Ising model in polynomial time, shouldn't be it's complexity same as the Ising model problem?
3. When I code it up using Mathematica (assuming $A = B = 1$) for the following two isomorphic graph pairs, I am getting false positives.

The graphs are:

![enter image description here](https://i.sstatic.net/S8lrJ.png) and ![enter image description here](https://i.sstatic.net/ViVWf.png).

For this pair of graphs, I get the following configurations which are correct isomorphisms and for them $H=0$. They are:

1. $x\_{1,1}, x\_{2,2}, x\_{4,3}, x\_{3,4}$
2. $x\_{4,1}, x\_{3,2}, x\_{1,3}, x\_{2,4}$
3. $x\_{1,1}, x\_{3,2}, x\_{4,3}, x\_{2,4}$
4. $x\_{4,1}, x\_{2,2}, x\_{1,3}, x\_{3,4}$

But when I evaluate the Ising formulation with all possible inputs using Mathematica, I get five more false positives along with these four. They are:

1. $x\_{1,4}, x\_{2,3}, x\_{3,2}, x\_{4,1}$
2. $x\_{1,4}, x\_{2,2}, x\_{3,1}, x\_{4,3}$
3. $x\_{1,3}, x\_{2,4}, x\_{3,1}, x\_{4,2}$
4. $x\_{1,1}, x\_{2,4}, x\_{3,3}, x\_{4,2}$
5. $x\_{1,4}, x\_{2,3}, x\_{3,1}, x\_{4,2}$

What am I missing?

**Tags:** reductions, graph-isomorphism, statistical-physics

> **Comments:**
> **username_1**: Isn't the complexity of the Ising model known, but known to be hard (e.g. NP-hard)? If it's hard, then the fact that GI reduces to something, say, NP-hard is not new or surprising and doesn't tell you anything new about the complexity of GI. (Also, just a small note: "not known and hence NP-intermediate" -> "not known and *conjecturally* NP-intermediate")  
> **username_0**: @JoshuaGrochow, the Ising model is NP-complete - a result of Sorin Istrail.  
> **username_0**: @JoshuaGrochow As the Ising model is known to be NP-Complete, any problem which can be reduced to Ising model in polynomial time should also be NP-Complete. Isn't it what is happening here?  
> **username_1**: Just the opposite: a problem L can be reduced to the Ising model if and only if L is in NP. If the reduction went the *opposite way* (the Ising model reduces to Graph Isomorphism), then that would say that GI is NP-complete (and therefore that PH collapses).  

---

## 1 answers

### Answer by username_2 on 2014-07-24. Score: 6 | Accepted answer

The counterexamples you give are not correct. I suspect your bug is this: when doing the sums over edges in (or not in) $E\_1$ and $E\_2$, you need to consider both orderings of each pair.

Consider your first false positive. One of the mismatched edges corresponds to (the lack of) $(2,4)$ in $G\_1$, which maps to $(3,1)$ in $G\_2$ (which is present). This makes the third term in the sum non-zero: consider $(i,j)$=$(2,4)$ and $(u,v)$=$(3,1)$; $x\_{3,2}x\_{1,4}$ is non-zero. If you only consider the edge pairs $(u,v)$ where $u

> **Comments:**
> **username_0**: following your suggestion, I was able to fix my objective function.  
> **username_0**: I also got correct result for a non-isomorphic pair following your suggestion.  
> **username_2**: Glad to have helped!  

---

