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.
