Clique Detection via Genetic Programming
Thomas D. Haynes, Dale A. Schoenefeld · The MIT Press eBooks · 1996
Genetic programming is applied to the task of finding all of the cliques in a graph. Nodes in the graph are represented as tree structures, which are then manipulated to form candidate cliques. The intrinsic properties of clique detection complicates the design of a good fitness evaluation. We analyze those properties, and show the clique detector is found to be better at finding the maximum clique in the graph, not the set of all cliques. Category: Genetic Programming 1 Introduction Determining whether an undirected graph contains a clique of size k is NP complete. In this paper, Genetic Programming (GP) [10] techniques are utilized to find cliques in a graph. A pure Genetic Algorithm (GA) approach was considered, but natural encodings resulted in variable length chromosomes. GPs are ideal for representing variable length chromosomes. A collection of cliques in a graph can be represented as a list of a list of nodes which, in turn, can be represented by a tree structure, as in Figu...