Parallel Algorithms for Finding Large Cliques in Sparse Graphs
arXiv:2109.09663 · doi:10.1145/3409964.3461800
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.
References in corpus (9)
- Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations
- On the maximum number of cliques in a graph
- Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries
- To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations
- GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra
- Log(Graph): A Near-Optimal High-Performance Graph Representation
- Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics
- Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems
- Parallel K-Clique Counting on GPUs