Maximal clique enumeration. (c2007)

Abstract

Maximal clique enumeration is one of the most important tools for solving problems in a wide variety of application domains. Classical enumeration techniques suffer from being too slow on large scale data. New techniques, introduced in the work of Abu-Khzam, decompose the input graph into a smaller subgraph and its complement in an attempt to reduce the search space and confine the exponential-time enumeration to subgraphs that are often small in practice. Such subgraphs are called dominating structures in our work. We discuss different dominating structures for the maximal clique enumeration problem, but we focus in our implementations on two of them. The first structure is a vertex cover of the input graph and the second one is a maximal matching of the complement of the graph. We consider these two edge capturing structures on graphs of different densities. Our experimental study revealed that the vertex cover approach is faster than the well-known Bron and Kerbosch (BK) algorithm on sparse graphs, as well as graphs whose vertex covers are small. Theoretical analysis supports our findings since the run time is improved from O(3n/3 ) to O(3k/3 ) , where k is the vertex cover size. Moreover, our second approach proved to be faster than BK on graphs of high density.