3
$\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
  • 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$ Jul 24, 2014 at 0:17
  • 1
    $\begingroup$ @JoshuaGrochow, the Ising model is NP-complete - a result of Sorin Istrail. $\endgroup$ Jul 24, 2014 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$ Jul 24, 2014 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$ Jul 24, 2014 at 18:05

1 Answer 1

6
$\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$
3
  • $\begingroup$ following your suggestion, I was able to fix my objective function. $\endgroup$ Jul 24, 2014 at 16:04
  • $\begingroup$ I also got correct result for a non-isomorphic pair following your suggestion. $\endgroup$ Jul 24, 2014 at 19:56
  • 1
    $\begingroup$ Glad to have helped! $\endgroup$ Jul 24, 2014 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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