Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time

By David Eppstein, Maarten Löffler, Darren Strash. Exact Complexity of NP-hard Problems, 2010

404 citations recorded by the source corpus.

The degeneracy of an n-vertex graph G is the smallest number d such that every subgraph of G contains a vertex of degree at most d. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron–Kerbosch algorithm and show that it runs in time O(dn3 d/3). We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an n-vertex graph with degeneracy d (when d is a multiple of 3 and n ≥ d + 3) is (n − d)3 d/3. Therefore, our algorithm matches the Θ(d(n − d)3 d/3) worst-case output size of the problem whenever n − d = Ω(n).

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/2907ef973b8e2c94b1c38f746a27b5685f1f4ce9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Simultaneous Denoising, Deconvolution, and Demixing of Calcium Imaging Data (2016, neutral): “methods effective for large sparse graphs exist for this problem (Eppstein et al., 2010).”
TEASER: Fast and Certifiable Point Cloud Registration (2020, methodology): “TEASER is implemented in MATLAB, uses cvx [118] to solve the convex relaxation (23), and uses the algorithm in [106] to find the maximum clique in the pruned TIM graph (see Theorem 6).”
Listing All Maximal Cliques in Large Sparse Real-World Graphs (2011, methodology): “esults¨ showing the algorithm to be good in practice as well as in theory. 1.1 Our Results We implement the algorithm of Eppstein, Lofﬂer, and Strash for listing all maximal¨ cliques in sparse graphs [13]. Using a corpus of many large real-world graphs, together with synthetic data including the Moo”
Truss Decomposition in Massive Networks (2012, methodology): “The k -core can be used as an effective heuristic for maximal clique enumeration [17], since a clique of size k must be in a ( k − 1) -core, which can be signiﬁcantly smaller than the original graph.”