Speaker: Virginia Vassilevska Williams (MIT)

Title: Clique listing algorithms

Abstract: A k-clique in a graph G is a subgraph of G on k vertices in which every pair of vertices is linked by an edge. Cliques are a natural notion of social network cohesiveness with a long history.

A fundamental question, with many applications, is “How fast can one list all k-cliques in a given graph?”.

Even just detecting whether an n-vertex graph contains a k-Clique has long been known to be NP-complete when k can depend on n (and hence no efficient algorithm is likely to exist for it). If k is a small constant, such as 3 or 4 (independent of n), even the brute-force algorithm runs in polynomial time, O(n^k), and can list all k-cliques in the graph; though O(n^k) time is far from practical. As the number of k-cliques in an n-vertex graph can be Omega(n^k), the brute-force algorithm is in some sense optimal, but only if there are Omega(n^k) k-cliques. In this talk we will show how to list k-cliques faster when the input graph has few k-cliques, with running times depending on the number of vertices n, the number of edges m, the number of k-cliques T and more. We will focus on the case when k=3, but we will note some extensions.

(Based on joint work with Andreas Bjorklund, Rasmus Pagh, Uri Zwick, Mina Dalirrooyfard, Surya Mathialagan and Yinzhan Xu)