Parallel algorithms for finding large cliques in sparse graphs
METADATA ONLY
Loading...
Author / Producer
Date
2021-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21)
Journal / series
Volume
Pages / Article No.
243 - 253
Publisher
Association for Computing Machinery
Event
33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2001)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Parallel graph algorithms; Clique listing; Arboricity; Degeneracy