On the efficiency of clique detection in graphs

This thesis examines the devices employed by various algorithms to search for maximal complete subgraphs in graphs. Also known as cliques, in Chapter 1 these subgraphs are seen to play an important role in graph theory, information retrieval, Sociometry, logic design, and computational complexity. The enumeration of cliques using the Harary-Rcss, Bonner, Peay, and Bron-Kerbosch algorithms is discussed in Chapter 2. The Reduced Redundancy algorithm is introduced, and the performance of the five procedures is assessed using an alternative approach to empirical testing. Each of the algorithms is shown to generate a "derivation tree" for a given graph whose size can be used as a measure of its efficiency. In Chapter 3, the possibility of exploiting vertex similarity is examined with a view to reducing the size of the derivation tree. As a consequence, algorithms are proposed for finding non-similar cliques. The concept of "complete subgraph equivalence" of vertices is introduced to develop a means for expressing the cliques of a graph as the Cartesian product of vertex subsets. An algorithm for detecting the existence of a clique of order k in a certain class of k-partite graphs in polynomial time is proposed in Chapter 4. This class consists of all graphs reducible by the algorithm to k-partite graphs having at most two vertices per block of degree greater than 0. This algorithm is shown to provide an efficient heuristic which can be used in a procedure for determining whether a well-formed formula is a tautology. The thesis is concluded with an empirical analysis of the techniques employed by the enumeration algorithms of Chapter 2. In addition, the efficiency of the Clique Detection algorithm is compared with that of the Reduced Redundancy algorithm.Science, Faculty ofComputer Science, Department ofGraduat