Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

L. Gianinazzi, M. Besta, Y. Schaffner, T. 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:
access preprint on arxiv:


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={7},
  booktitle={Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21)},
  publisher={ACM},
  doi={10.1145/3409964.3461800},
}