Listing maximal cliques

I don't have to list all the reasons why it's important to find all the maximal cliques in a graph, I think, but I heard a new one today (a form of social network analysis): one of the lecturers in my department wants to find cliques in a graph representing similarities between homework assignments of different students in the same class. You can guess why...

Anyway, I have a new preprint out with Maarten Löffler and Darren Strash on exactly this problem: "Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time", arXiv:1006.5440. The main piece of background for our paper is the Bron–Kerbosch algorithm, a simple recursive backtracking procedure for listing all maximal cliques which works well in practice but which has only limited theoretical bounds on its performance. As the original Bron & Kerbosch paper already observed, a strategy known as "pivoting" helps to control the number of recursive calls at each step of the algorithm, and Tomita, Tanaka, and Takahashi showed that with careful choices of pivots the algorithm could be made to run in time at most equal to the worst-case bound on the number of maximal cliques in an \( n \)-node graph, \( 3^{n/3} \).

The new paper suggests a different strategy for improving the running time of the Bron–Kerbosch algorithm: choose the order of the recursive calls carefully. In particular it works well (according to our analysis) to add vertices to a partial clique in order by their degrees: first try adding the vertex with the smallest degree, second try the vertex whose degree in the remaining subgraph is smallest, etc. Doing this at the top level of the recursion (without pivoting), and then switching to the Tomita et al. pivoting strategy at lower levels, leads to a time bound that is linear in any sparse family of graphs (such as the planar graphs) and that has near-optimal dependence on the degeneracy of the graph, a standard measure of its sparseness.

The modified version of the Bron–Kerbosch algorithm is still very simple, and (we hope) practical, but we have not yet had a chance to perform any experimental tests to determine how much the vertex ordering helps the algorithm in practice.

Comments: