Two Algorithms to Find all Maximal Cliques on Graphical Processing Units (GPUs)

Two new algorithms are presented to find all the maximal cliques in an undirected graph. The algorithms are not recursive and they have been designed to take advantage of the large number of cores available in Graphical Processing Units (GPUs). The proposed algorithm evaluates all elements of the Power Set of the set of vertices, in other words, all the possible subsets of the set of vertices and finds for each of them, in parallel, if that particular subset is a clique. Once all cliques have been found, the cliques that are not maximal are eliminated. The algorithms differ in the way the non-maximal cliques are discarded. In one version, as soon as one subset of vertices has been identified as being a clique, the code checks if this is a maximal clique. In the other version, all the cliques are brought to the host computer and the cliques that are subsets of other cliques are discarded. Prototype implementations have been written using Thrust. Results of experiments are included. The code can be easily adapted to solve the dual problem of the maximal cliques problem: The maximal independent sets problem.