Parallel Clique Counting and Peeling Algorithms

Understand

We present a new parallel algorithm for $k$-clique counting/listing that has polylogarithmic span (parallel time) and is work-efficient (matches the work of the best sequential algorithm) for sparse graphs.

• Our algorithm is based on computing low out-degree orientations, which we present new linear-work and polylogarithmic-span algorithms for computing in parallel.
• We also present new parallel algorithms for producing unbiased estimations of clique counts using graph sparsification.
• Finally, we design two new parallel work-efficient algorithms for approximating the $k$-clique densest subgraph, the first of which is a $1/k$-approximation and the second of which is a $1/(k(1+\epsilon))$-approximation and has polylogarithmic span.