2
$\begingroup$

I am going to through Ising formulations of many NP problems 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 and enter image description here.

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?

$\endgroup$
  • 4
    $\begingroup$ 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") $\endgroup$ – Joshua Grochow Jul 24 '14 at 0:17
  • 1
    $\begingroup$ @JoshuaGrochow, the Ising model is NP-complete - a result of Sorin Istrail. $\endgroup$ – Omar Shehab Jul 24 '14 at 8:37
  • $\begingroup$ @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? $\endgroup$ – Omar Shehab Jul 24 '14 at 16:05
  • 2
    $\begingroup$ 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). $\endgroup$ – Joshua Grochow Jul 24 '14 at 18:05
5
$\begingroup$

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<v$, you miss counting these non-zero terms and get the incorrect zero result.

$\endgroup$
  • $\begingroup$ following your suggestion, I was able to fix my objective function. $\endgroup$ – Omar Shehab Jul 24 '14 at 16:04
  • $\begingroup$ I also got correct result for a non-isomorphic pair following your suggestion. $\endgroup$ – Omar Shehab Jul 24 '14 at 19:56
  • 1
    $\begingroup$ Glad to have helped! $\endgroup$ – William Whistler Jul 24 '14 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.