Lukas Gianinazzi, Maciej Besta, Yannick Schaffner, Torsten Hoefler:
Parallel Algorithms for Finding Large Cliques in Sparse Graphs
(In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21), ACM, Jul. 2021)
Abstract
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.
Documents
download article:
Recorded talk (best effort)
BibTeX
@inproceedings{gianinazzi-spaa21-KClique, author={Lukas Gianinazzi and Maciej Besta and Yannick Schaffner and Torsten Hoefler}, title={{Parallel Algorithms for Finding Large Cliques in Sparse Graphs}}, year={2021}, month={Jul.}, booktitle={Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21)}, publisher={ACM}, source={http://www.unixer.de/~htor/publications/}, }
