Solving Vertex Cover via Ising Model on a Neuromorphic Processor

Abstract

Neuromorphic architectures are characterized by a network of asynchronous computation units that resemble the behavior of neurons in the brain. With much interest devoted to how these architectures can be utilized in learning and intelligent systems, we note that the massive parallelism of neuromorphic architectures can also be leveraged to solve some NP problems more efficiently than on a von Neumann architecture. In this work, we demonstrate how a neuromorphic processor can be used to solve the classic vertex cover problem via an Ising spin model. Mapping the Ising model to a neural architecture itself requires solving two NP-hard problems at initialization, for which we use approximate solutions. The maximum fan-in and fan-out constraint, common on many neuromorphic processors, requires a graph partitioning, and solving the time-dependency constraints in updating the graph amounts to a graph coloring problem. As a result, space and time efficiency is decreased only by a constant factor without degrading solution quality.