# Parallel Algorithms for Finding Large Cliques in Sparse Graphs

arXiv: https://arxiv.org/abs/2109.09663 · HTML: https://mlsanity.com/paper/2109.09663/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2021.

## Built on by (most cited first, 7 of 7)

- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [CliquePH: Higher-Order Information for Graph Neural Networks through Persistent Homology on Clique Graphs](https://mlsanity.com/paper/2409.08217/) (2024)
- [Fast Maximum k-Plex Algorithms Parameterized by Small Degeneracy Gaps](https://mlsanity.com/paper/2306.13258/) (2023)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)

## Abstract (arXiv)

We present a parallel k-clique listing algorithm with improved work bounds (for the same depth) in sparse graphs with low degeneracy or arboricity. We achieve this by introducing and analyzing a new pruning criterion for a backtracking search. Our algorithm has better asymptotic performance, especially for larger cliques (when k is not constant), where we avoid the straightforwardly exponential runtime growth with respect to the clique size. In particular, for cliques that are a constant factor smaller than the graph's degeneracy, the work improvement is an exponential factor in the clique size compared to previous results. Moreover, we present a low-depth approximation to the community degeneracy (which can be arbitrarily smaller than the degeneracy). This approximation enables a low depth clique listing algorithm whose runtime is parameterized by the community degeneracy.