On neural networks for graph isomorphism problem
K. Agusa, Shigetaka Fujita, Masafumi Yamashita, T. Ae · 1992
Although the Hopfield neural networks is known to provide an efficient algorithm for hard problems, it cannot always give the correct solution due to local minima. For the graph isomorphism problem (which has not yet been proved to be polynomially solvable or NP-complete), the authors first introduce a Hopfield network that shows a similar behavior, and give some additional initial conditions, which are collectively called condition C. However, the Hopfield network with condition C is still not powerful enough. The authors introduce another type of neural network and show that it can solve the problem correctly at least for small graphs.>