- Conference Paper
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. Show more
Book titleProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21)
Pages / Article No.
PublisherAssociation for Computing Machinery
SubjectParallel graph algorithms; Clique listing; Arboricity; Degeneracy
MoreShow all metadata