A Discrete Neural Algorithm for the Maximum Clique Problem: Analysis and Circuit Implementation

For the Maximum Clique problem we propose a neural approximation algorithm that can be implemented on Field Programmable Gate Arrays (FPGA). The algorithm builds a sequence of discrete Hopfield networks that, in polynomial time, converge to a state representing a clique for a given graph. Some experiments made on the DIMACS benchmark show that the approximated solutions found are satisfactory. Moreover the simplicity of the algorithm makes it easy to design a uniform family of circuits of small size (ß 10n 2 log n). 1. Introduction Computing the size of the largest clique in a graph G, i.e., the maximum subset of vertices of G such that every two vertices are joined by an edge (Max Clique problem), is one of the first problems shown to be NP-complete [7]. More recently, Feige et al. [2] showed that even approximating this problem within a constant factor is NP-hard. In particular, if NP 6= ZPP, no polynomial time algorithm can approximate Max Clique within a factor n 1\Gamma" for ..