Neural Network Models for the Maximum Clique Problem

Abstract

ABSTRACT: In this paper we describe two neural network based algorithms for the Maximum Clique Problem. The developed algorithms provide discrete and continuos descent dynamics respectively to approximate the solution of the quadratic 0-1 formulation of the Maximum Clique Problem. The discrete approach performed better, maintaining computational competitiveness to greedy randomized search procedures. Experimental results on test graphs of size up to 3361 vertices and 5506380 edges are presented.

RESUMEN: Se describen dos algoritmos basados en redes neuronales para el Problema del Clique Máximo de un grafo. Los algoritmos desarrollados implementan dinámicas descendentes, en un caso continua y en el otro discreta, para aproximar la solución del problema planteado a partir de la formulación cuadrática del mismo. El algoritmo discreto presenta un mejor desempeño, alcanzando resultados similares a los obtenidos con otras heurísticas. Se discuten los resultados de la aplicación de los algoritmos en un conjunto de grafos de hasta 3361 vértices y 5506380 aristas.