Approximating maximum clique with a Hopfield network
- 1 May 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 6 (3) , 724-735
- https://doi.org/10.1109/72.377977
Abstract
In a graph, a clique is a set of vertices such that every pair is connected by an edge. MAX-CLIQUE is the optimization problem of finding the largest clique in a given graph and is NP-hard, even to approximate well. Several real-world and theory problems can be modeled as MAX-CLIQUE. In this paper, we efficiently approximate MAX-CLIQUE in a special case of the Hopfield network whose stable states are maximal cliques. We present several energy-descent optimizing dynamics; both discrete (deterministic and stochastic) and continuous. One of these emulates, as special cases, two well-known greedy algorithms for approximating MAX-CLIQUE. We report on detailed empirical comparisons on random graphs and on harder ones. Mean-field annealing, an efficient approximation to simulated annealing, and a stochastic dynamics are the narrow but clear winners. All dynamics approximate much better than one which emulates a "naive" greedy heuristic.Keywords
This publication has 21 references indexed in Scilit:
- A note on the approximation of the max clique problemInformation Processing Letters, 1991
- A theoretical investigation into the performance of the Hopfield modelIEEE Transactions on Neural Networks, 1990
- A NEW METHOD FOR MAPPING OPTIMIZATION PROBLEMS ONTO NEURAL NETWORKSInternational Journal of Neural Systems, 1989
- Stereo correspondence through feature grouping and maximal cliquesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Graph theoretic algorithms for the PLA folding problemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- Labeled point pattern matching by Delaunay triangulation and maximal cliquesPattern Recognition, 1986
- Finding a Maximum Clique in an Arbitrary GraphSIAM Journal on Computing, 1986
- Lower bounds on the independence number in terms of the degreesJournal of Combinatorial Theory, Series B, 1983
- Cliques in random graphsMathematical Proceedings of the Cambridge Philosophical Society, 1976
- An Analysis of Some Graph Theoretical Cluster TechniquesJournal of the ACM, 1970