{'fraction_non_alphanumeric': 0.04699843148438614, 'fraction_numerical': 0.01417367745615286, 'mean_word_length': 4.088666376433029, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parallel Algorithms for Finding Large Cliques in Sparse Graphs

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.


INTRODUCTION
Finding large cliques has many applications in the social sciences, bioinformatics, computational chemistry, and others [1,8,12,23,33,34,43,48,51,52]. As the problem is NP-hard and remains hard even when parameterized by the size of the clique [28], it makes sense to consider special families of graphs for which the problem is tractable. If the work of an algorithm can be written as O ( ( ) ) (for some function of the parameters and some polynomial of the input size ), the problem is fixed parameter tractable (FPT) with respect to the parameters [27]. The clique problem is FPT with respect to certain structural sparsity parameters of graphs.
As a classic example family of sparse graphs, planar graphs do not contain cliques with more than 4 vertices, and all cliques in a planar graph can be listed in linear time in the size of the graph [42]. Planar graphs are members of a more general class of sparse graphs for which every subgraph has a low-degree vertex. This notion of sparsity is called degeneracy. A closely related family of sparse graphs is defined by being decomposable into a small number of forests. The arboricity measures the number of such forests required for a given graph. Many real-world graphs are sparse [5,6,[9][10][11]14] and have a low degeneracy and arboricity [4,7,25,49,50].
In this work, we focus on improving the work and depth of FPT algorithms to list all -cliques in these sparse graphs, improving both work and depth significantly as a function of the clique size . Our approach utilizes the notion of edge communities -vertices with whom an edge forms a triangle. We further introduce a notion of relevant edges, that effectively upper bounds the community's size. This enables us to reject edges that cannot be a part of a -clique, pruning unnecessary recursive calls. We show that this pruning criterion asymptotically reduces the work compared to previous approaches.

Preliminaries
We consider a (directed or undirected) graph = ( , ) with vertices and edges . We will generally assume the graph is connected and therefore = Ω( ). To orient a graph by a total order, direct its edges from the endpoint lower in the total order to the endpoint higher in the total order. A graph that has been oriented by a total order is acyclic by construction. The subgraph of a graph induced by a vertex set ′ is [ ′ ]. The neighbors of a vertex in the graph are the set of all vertices in that are connected to by edges in . In a directed graph, the out-neighbors are + ( ) = { ∈ | ( , ) ∈ }, and the in-neighbors are − ( ) = { ∈ | ( , ) ∈ }. If the graph is clear from the context, we write ( ), + ( ), and − ( ) for short.
In an undirected graph, the community ( , ) = ( ) of an edge = { , } is the intersection of the neighbors of its endpoints. In a directed graph, the community ( , ) = ( ) of an edge = ( , ) is the intersection of the out-neighbors of and the inneighbors of . If the graph is clear from the context, we write ( , ) and ( ) for short.
Sparse Graphs. A graph = ( , ) is -degenerate, if in all induced subgraphs of , there is a vertex with degree at most [37]. The degeneracy of a graph is the smallest such that the graph is -degenerate. Note that an -degenerate graph can have an unbounded maximum degree. For example, the star graph is 1-degenerate but has a maximum degree of − 1. An -degenerate graph can be oriented such that every vertex has at most outneighbors (greedily remove a vertex with the smallest degree in the remaining subgraph). The order in which this greedy procedure removes vertices is a degeneracy order.
A graph = ( , ) is -community degenerate, if every (nonedgeless) subgraph ′ has an edge with | ′ ( )| ≤ . The community degeneracy of a graph is the smallest value , such that the graph is -community degenerate [18]. The community degeneracy is strictly smaller than the degeneracy: < and there are families of graphs where the community degeneracy is asymptotically smaller. For example, the -dimensional hypercube has degeneracy = , but community degeneracy = 0. Moreover, the community degeneracy can be 1 for graphs where the degeneracy is Θ( ) and there are Θ( ) triangles. This is the case for a graph which has the complete bipartite graph as a subgraph, with /2 vertices in each part, and additionally one part of the graph induces a line graph on /2 vertices. Buchanan et al. [18] also show empirically that the community degeneracy is significantly smaller (27%-80%) than the degeneracy for some real-world graphs (when the degeneracy is significantly larger than the clique number).
The smallest number of forests into which a graph can be decomposed (meaning that every edge is in exactly one of the forests) is the arboricity of a graph. It is closely related to the degeneracy, in particular ≤ < 2 [41].
-Cliques. An induced subgraph of that is a complete graph with -vertices is a -clique. It follows from the definition that an -degenerate graph does not contain any ( + 2)-clique and a graph with arboricity does not contain any (2 + 1)-clique (using > /2). In this paper, we generally assume ≥ 4. Deciding the size of a maximum clique is a classic NP-hard problem [31] and so is deciding if the graph has a -clique. The problem of finding a clique of size remains hard when parameterized by : it is W[1]-hard [28]. However, the problem becomes FPT for graphs when parameterized by degeneracy or arboricity [21].
Model of Computation. Our execution model is a shared-memory parallel computer with concurrent reads and exclusive writes (CREW PRAM) [44]. We express the performance of our algorithms in the work/depth model. The work is the total number of elementary operations performed by all processors in any algorithm execution. The depth is the length of a critical path. An algorithm with work and depth can be scheduled on a CREW PRAM with processors so that it takes ( / + ) time steps [15,44].

Related Work
Chiba and Nishizeki [21] presented a result on -clique listing for low arboricity graphs. Their algorithm takes ( −2 ) work.
Danish et al. [25] gave improved bounds in terms of the degeneracy. Their algorithm does ( ( 2 ) −2 ) work. Since ≤ < 2 , this is never worse than Chiba and Nishizeki's work bound, but can be faster by a term exponential in for graphs where the degeneracy is close to the arboricity. The algorithm has a depth of ( ), stemming from how the graph is directed with a degeneracy order. Recently, Shi et al. [49] gave a variant on the algorithm that uses a fast parallel approximation to the degeneracy order (in addition to providing some improvements in the data structure used to represent the graph during the recursive search). When is constant (which they assume), this approximation does not impact the runtime. However, the work increases by a factor exponential in because of this approximation. These -clique listing algorithms are not well suited to finding very large cliques, as their bounds become superexponential in (and ) when the size of the cliques is = Ω( ). This is far from optimal, as a graph with degeneracy has at most ( − + 1)2 cliques overall [55]. Previous -clique listing algorithms [21,25,49] use a backtracking scheme combined with a clique-growing pattern, where a subgraph is expanded into larger and larger cliques, until a -clique is found or determined to be unreachable. A common optimization [25,49] is to orient the input graph. In -clique counting, one usually orients a graph with a total order on the vertices [25,49]. A popular choice of order is the degeneracy-order as it assigns low out degrees and can be computed in linear time [38]. Other works on -cliques focus on reordering heuristics [36], using GPUs [2].
Listing maximal cliques is also a subject of numerous works [16,19,20,40,47]. For example, Eppstein [29] presents a variant of Bron-Kerbosch's algorithm [17,53] to find maximal cliques. It takes  Figure 1: To support a -clique, an edge must have − 2 triangles that contain it. In other words, its community must have a size of − 2. In the example, the community of the edge { 1 , 2 } contains all the other vertices { 3 , 4 , 5 , 6 }. Hence, it could potentially support a 6-clique. Indeed, the edge { 1 , 2 } does support a 6-clique.

O
3 /3 time, which is close to the ( − )3 /3 lower bound [29] on the number of maximal cliques in an -degenerate graph. A maximum clique can be computed in O 2 0.276 time from the relationship to maximum independent sets [45].
Converting a graph to a directed, acyclic graph gives an effective way to assign cliques to certain vertices: A clique can e.g., be associated with its topologically smallest or largest vertex. This way, double counting can be avoided and the directions reduce the size of the search space.

Our Contributions
We present an algorithm that provides, for the same depth, improved work bounds for -clique counting in -degenerate graphs. In particular, when = Ω( ), the improvement grows exponentially with . Considering the case where is not constant is important because that is when the problem becomes hard. See Table 1 for a comparison of our bounds compared to previous -clique listing results in sparse graphs. Our algorithm differs in two relevant aspects from previous approaches [21,25,49].
First, existing approaches use the degree of a vertex to decide whether the neighborhood of a vertex can contain a smaller clique. In contrast, our algorithm looks at edges and their triangles to grow the clique: Each edge of a -clique participates in (at least) − 2 triangles. See Figure 1 for an example. Our algorithm preprocesses the graph such that each triangle ( , , ) is supported by exactly one of its edges. If edge ( , ) supports triangle ( , , ), we say that vertex is in the community of edge ( , ). To find a -clique, we only need to consider edges that support at least − 2 triangles. We add this edge to the clique and recursively search for a ( −2)-clique in the subgraph induced by the community of that edge.
Second, we observe that we can use the number of vertices ordered between the endpoints of an edge as a proxy for the number of triangles it supports, as illustrated in Figure 2. This observation allows us to exclude edges from the search space because they cannot support a -clique, without actually looking at their triangles in every step. Moreover, this simplification enables us to upper  Figure 2: If the graph is oriented by a total order, we can use the number of vertices ordered between the endpoints of an edge as a proxy to determine if it can support aclique. If there are less than − 2 vertices ordered between the endpoints, the edge cannot support a -clique. In the example, only the edge ( 1 , 6 ) could support a 6-clique using this pruning rule. Therefore, we call the edge relevant. However, the graph only contains two 5-cliques and no 6-clique because there is no edge ( 3 , 4 ).
bound our algorithm's work, improving on the state-of-the-art for -clique counting in -degenerate graphs.
Pruning edges by excluding those which do not have enough vertices ordered between their endpoints is what is responsible for We also discuss different ways to orient and preprocess the graph. These graph orientations leads to three variants with different work/depth tradeoffs, as seen in Table 1.
Finally, we show clique counting results parameterized by the community degeneracy. Our algorithm uses a total order on the edges in addition to a total order on the vertices to get better results for graphs where < − 1. We again get three variants with different work/depth tradeoffs. To achieve the sublinear-depth variants, we present a novel low-depth approximation algorithm for the community degeneracy.

COMMUNITY-CENTRIC CLIQUE LISTING
We begin with an informal description of the ideas behind our community-centric clique listing algorithm. Afterward, we state the algorithm and bound its work and depth. Let us start with a simple observation about -cliques, on which we will gradually expand. Any induced subgraph on a clique is a clique as well. A slight reformulation of this observation is the primary building block of the algorithm by Chiba and Nishizeki [21], and subsequently, of Danisch et al. [25] and Shi et al. [49]: If a vertex's neighborhood contains a ( − 1)-clique, then we have found a -clique [21]. This insight allows a simple backtracking formulation, where one recursively searches for smaller cliques in the local neighborhood of vertices. In the practical implementations [21,25,49], this formulation gives rise to a form of candidate growing. In each recursive call, the current candidate motif grows by one vertex to a larger clique. During the backtracking, the candidate motif shrinks again.
Observe that one is not limited to grow a motif by a single vertex in each step, but can extend the motif by any kind of clique in its neighborhood, such as an edge (i.e., a 2-clique). Whereas each Work Depth Our Results for Degeneracy §2: Our Results for Community Degeneracy §2: Table 1: Bounds for listing all -cliques in a graph ( ≥ 4) with degeneracy , community degeneracy , and arboricity . The parameter is some positive real constant. Recall that ≤ < 2 and ≤ + 2 ≤ + 1. Bounds marked with † hold in expectation and those marked with ★ hold with high probability in .
vertex has a fixed number of neighbors, each edge belongs to a fixed number of triangles. In a -clique, each edge participates in − 2 triangles. If the clique is oriented by a total order, we can refine the statement. The supporting edge of a -clique in a graph oriented by a total order is the edge connecting the first and last vertex in the total order. It holds that: Observation 1. The supporting edge of a -clique oriented by a total order, has a community ( ) of size at least − 2. All other edges have a smaller community.
In Section 2.2, we show the following bounds for our algorithm: Theorem 2.1. Let = ( , ) be a directed acyclic graph oriented by a total order, such that its largest community has size and its largest out-degree is˜. Then, the work performed by Algorithm 1 is and its depth is O log 2 + log .
In Section 4, we discuss different approaches to to orient a graph, leading to the work/depth tradeoffs in Table 1.

Algorithm Construction
Algorithms 1 and 2 summarize our clique listing algorithm. Input to Algorithm 1 are a graph Dag oriented by a total order and an integer The recursive procedure is shown in Algorithm 2. As input, it takes a directed graph Dag, a set of candidate vertices and a constant > 0, stating the number of vertices still required to complete a -clique. The recursion has two base cases: for = 1 (line 2), where each vertex in the candidate set completes the partial motif to a -clique and for = 2 (line 4), where each connected pair of vertices completes the -clique.
Given a set of vertices with a total order, the distance function : × ↦ → {0, . . . , | − 2|} maps each pair of vertices ( , ) to the number of elements in that are ordered between and in the total order. We keep the set in a sorted array. Then, for any two candidates and , we compute ( , ) from their indices in .
In the recursive case, iterate over all vertex pairs ( , ), whose distance ( , ) to each other, given the total order and the candidate set , allows them to support a -clique (line 6). For each such pair, probe the existence of the corresponding edge (line 7) and, if successful, intersect the candidate set with the community of the edge (line 8) to create a new candidate set ′ . Then, make the next recursive call with the new candidate set ′ , requiring − 2 vertices to complete a -clique (line 9).
See Figure 3 for an example of an execution of Algorithm 1.

Work/Depth Analysis
Let us first bound the cost of the preprocessing in Algorithm 1. We can compute the triangles of a graph in (˜) work and (log 2 ) depth [49], which gives us the communities. Sorting the communities takes O ( log ) work and O (log ) depth [22]. We build for each edge an adjacency matrix of [ ( )] and rename the vertices to be consecutive integers. Next, for each edge ′ in such a subgraph [ ( )], we build a boolean indicator table for the vertices in its    for a 6-clique in the above graph. Black vertices belong to the candidate set for the next call to Algorithm 2, red vertices and edges are being considered for extending the clique, and grey vertices and edges have been already visited. Before we bound the work and depth of the recursive Algorithm 2, we need some additional notation. Given a set of vertices , a pair ( , ) of vertices is relevant with respect to ∈ N 0 , if and only if ( , ) ≥ , meaning that there are at least vertices ordered between and . The set of relevant pairs of with respect to and the total order of is R ( ). An edge = ( , ) is relevant with respect to , if it forms a relevant pair with respect to . Note that an edge that is not relevant with respect to −2 cannot support a -clique and that Algorithm 2 only recurses on the relevant edges (with respect to − 2). The set of relevant edges with respect to in the graph = ( , ) is R ( ). See Figure 4 for an illustration of the relevant pairs and edges.
Next The recursion in Algorithm 2 has depth ⌊ −2 2 ⌋. Hence, the critical path has length O (log + + log( + 1)). As long as ≠ 0, the additive term is negligible. Next, we express the work of Algorithm 2 recursively.
Let ( , ) be the work of Algorithm 2 for candidate set and parameter . We express the work recursively as follows: By telescoping this formula, we can see that the key to tackling this recursion is a bound on the following sum: ∑︁ The sum corresponds to the loop in the algorithm that iterates over the relevant edges. For each edge , the term |R −2 ( [ ( )])| is a bound on the number of relevant edges in the subgraph that the algorithm recurses on. In Section 3, we establish the following bounds on this quantity. We focus on bounding the total cost incurred for listing the cliques at the leaves of the recursion for ≥ 2. The proofs bounding the remaining cost (associated with the computation of intersections and edge testing) are similar and can be found in Appendix A.1.
For some constant , we define the following function to help unifying the analysis when is even or odd: The constant is chosen such that the work to list a -clique is at most and the cost of listing = | | -cliques is at most · · . Lemma 2.3. Let ( , ) be the work of the algorithm incurred at the leaves of the recursion in Algorithm 2. Then, we have for any ≥ 2, Proof. The proof is by induction on . The base cases = 2 and = 3 are quickly verified. Assume now, that the inequality on ( ′ , ) holds for all ′ ≤ . We show that it also holds for + 2.

COMBINATORICS
In this section, we prove Lemma 2.3, which is the key ingredient in the work proof. We begin by introducing the notation that we need for the proof. See also Figure 5 and Figure 6 for an illustration of the relevant concepts.

Additional Notation
A vertex ∈ is a relevant out-vertex with respect to , if there exists a vertex ∈ , such that ( , ) forms a relevant pair with respect to . The set of relevant out-vertices with respect to and the total order in is denoted P + ( ). Similarly, a vertex ∈ is a relevant in-vertex with respect to , if there exists a vertex ∈ , such that ( , ) forms a relevant pair with respect to . The set of  relevant in-vertices with respect to and the total order in is denoted P − ( ). See Figure 5 for an example.
E + ( ) are all relevant out-vertices with respect to , that are part of a relevant edge, not only a relevant pair. Similarly, E − ( , ) are all relevant in-vertices with respect to , that form a relevant edge together with , see Figure 6. Formally, we have: For a set and a predicate , we write [ ] to select the subset of that satisfies the predicate , e.g., [< ] contains all vertices in smaller than in the order <.

Bounds on Relevant Edges and Pairs
Let us begin with two simple observations on relevant pairs: Observation 3. In a set of vertices with a total order, the number of relevant out-and in-vertices with respect to ∈ N 0 is: Proof. The last (respectively first) ( + 1) vertices in cannot be relevant with respect to . □ Observation 4. In a set of vertices with a total order, the number of relevant pairs in with respect to ∈ N 0 is: Proof. The first relevant out-vertex forms relevant pairs with exactly | | − ( + 1) other vertices. The second out-vertex with | | − ( + 2) vertices, and so on, until the very last relevant outvertex only participates in one relevant pair. The count of relevant pairs is thus a sum over a descending sequence from | | − ( + 1) down to 1. Since there are |P + ( )| = | | − ( + 1) terms, the sum can be computed with Gauss' sum formula. A symmetric argument relates the relevant in-vertices to the relevant pairs. □ We continue with a simpler (weaker) Lemma related to Lemma 2.2: Lemma 3.1. For a graph = ( , ) oriented by a total order where the largest community has size and any ≥ 2, we have that: Proof. Every relevant edge is also a relevant pair, so we bound the number of relevant pairs |R −2 ( ( ))| for each edge . For any edge ∈ , by Observation 4 and | ( )| ≤ , □ When applied to a graph with at most + 2 vertices, Lemma 2.3 provides a factor 2 better bound than Lemma 3.1. This factor is crucial for the work bound as it will be amplified exponentially with by the recursion. Now, let us turn to the proof of our main result on counting relevant edges.
Proof Of Lemma 2.2. For each term of the sum, we rewrite |R −2 ( ( ))| using Observation 4. Note that | ( )| ≤ − 2 to upper bound the term: Now, we relate the set of relevant in-vertices that are part of a relevant edge to a set of vertices that are part of a relevant pair: Moreover, for every vertex that is in E − ( , ) and is not in Above, the inner sum now counts all pairs in + ( ), that are relevant with respect to − 1. We rewrite the sum using Observation 4 applied to the subgraph of induced by + ( ) (which has at most − 1 vertices): In the second step, we upper bounded |P − −1 + ( ) | using Equation (4). The sum now counts again over the edges, relevant with respect to , which concludes the proof. □

GRAPH ORIENTATION
Our clique listing algorithm requires a vertex ordering such that when we orient the graph, its communities have a small size . We explore three different approaches. The first two approaches rely on existing results on degeneracy orders. The third hybrid approach uses a different outer loop to achieve a better work/depth tradeoff for large cliques . We also present how to get algorithms with bounds that are parametric in the community degeneracy. These algorithms require an order on the edges that reduces the size of the subgraphs used in the recursive calls over the edges' communities.

Computing a Degeneracy Order
We can use previous results on degeneracy order to compute such an order, with different work/depth tradeoffs. A greedy algorithm computes the degeneracy order in linear time, but has linear depth. Although no low depth algorithm is known to compute the degeneracy order, it can be approximated effectively in parallel. A total order on the vertices such that the graph oriented by it has maximum out-degree is a -approximate degeneracy order. Note that the size of the largest community is at most the maximum out-degree minus 1. Hence, using these vertex orders to orient the graph, we obtain two of the results in Table 1 from Theorem 2.1, namely the best work and the best depth results for degeneracy.

The Hybrid Approach
While computing the exact degeneracy order provides the best work-bound in terms of , , and , its depth is linear in . Using an approximate degeneracy order yields a clique counting algorithm that is work-inefficient by a term that is exponential in . This inefficiency persists even for very small because the approximation leads to a factor 2 + larger maximum out-degree in the worst case. Hence the factor Θ((2 + ) ) work-inefficiency arises.
Therefore, we present a hybrid approach that is only workinefficient by a factor ≤ and has a depth that reduces the term linear in to linear in . The idea is that an approximate degeneracy order already guarantees that the subgraphs induced by the out-vertices have ( ) vertices. It then remains to solve these subgraphs with the clique listing algorithm that uses an exact degeneracy order. The algorithm goes as follows: Compute a (2.5)-approximate degeneracy order in parallel and orient the graph according to it. Then, for each vertex , orient the graph [ + ( )] using an (exact) degeneracy order, then run

Parameterizing by Community Degeneracy
Next, we present a preprocessing approach that uses a total order of the edges in addition to an order on the vertices. This preprocessing naturally leads to algorithms whose runtime is parameterized by the community degeneracy of the graph. To reduce the runtime for the recursive clique listing algorithm, we want to reduce the size of the subgraphs induced by the communities of an edge. We observe that it suffices to recurse only on a subset of the community, namely we can introduce an order on the edges of the graph. Then, we only consider the community of an edge in the subgraph induced by edges ordered higher than . In other words, these are the endpoints of the triangles supported by edges whose other edges come after the supporting edge. The approach is summarized in Algorithm 3 and goes as follows: In addition to computing a total order on the vertices, first, compute a total order ⪯ on the edges. Then, traverse the edges in this order and for each edge = ( , ) construct the candidate set ( , [ ⪯]) ( ), that is, the community of the edge in the subgraph of consisting of the edges ordered after in the total order. For each candidate set, run the recursive clique counting Algorithm 2 with parameter = − 2.
To reduce the work of this algorithm, the chosen edge order is crucial. We minimize the maximum size of the candidate sets with a greedy algorithm: repeatedly choose and remove an edge that support the smallest number of triangles in the remaining subgraph. By definition of the community degeneracy , the largest subgraph constructed in this way has vertices. Note that the order of the vertices used for the recursive clique listing does not influence the runtime and can be arbitrary (say by vertex id). Observe that the set of candidates ′ constructed for edge is a subset of the community ( ) of in the input graph. Moreover, each -clique is contained in at least one of the constructed subgraphs, namely the one which corresponds to the edge in the clique lowest in the community degeneracy order. The total order on the vertices ensures that each clique is reported exactly once. The analysis is basically the same as in Appendix A.2, except that we have a better bound for the induced subgraphs given by the maximum size of | ′ | = .
We again propose three different variants on implementing the preprocessing in Algorithm 3. The simplest way is the greedy approach outlined above, which leads to the best work.
The problem with this approach is that it has linear depth in to compute the edge order. Instead of computing the order of the edges greedily, we can compute an approximation of the order, summarized in Algorithm 4 and described in the following: Compute the triangles in . For each edge, keep track of the triangles that contain it (and vice versa). Moreover, for each edge , keep a count of the remaining number of triangles | ( )| that contain . Then, repeat the following until the graph has no edges left: Select all the edges with | ( )| ≤ (3 + ) / triangles. The constant must be positive. Remove those edges from the graph and add them to the total order, breaking ties arbitrarily. For each triangle that contained an edge in the removed set of edges, its edges need to update their count | ( )|. Then, update the overall count of remaining triangles .
Next, we make a few observations to help us bounding the work, depth, and quality of the approximate community degeneracy order.
Observation 5. A graph with community degeneracy has at most triangles.
Proof. Remove the edges of the graph in a greedy manner, picking the edge with the smallest remaining number of triangles that contain it next. By definition of the community degeneracy, each subgraph encountered this way has an edge with triangles that ′ ← the edges with at most | ( )| ≤ (3 + ) / triangles. 5: Add the edges in ′ to the total order, break ties arbitrarily. 6: Remove ′ from the graph 7: Update each ( ) to reflect the removal of ′ . 8: Update the number of triangles . 9: end while contain it. The process terminates after steps. Hence, the process removes at most triangles until no triangle is left. □ Observation 6. Algorithm 4 terminates after O log 1+ iterations Proof. From Observation 5, it follows that the average number of triangles per edge is at most 3 / in each iteration (each triangle is counted once for each of its edges). From any set of numbers, at most a 1 1+ fraction of numbers are larger than (1 + ) times the average. Hence, each iteration reduces the number of edges by a factor at least (1 + ). □ Proof. Listing the triangles takes O ( ) work and O log 2 depth [21]. Each iteration of the loop takes work proportional to the number of removed edges and O (log ) depth. By Observation 6, the algorithm terminates after O log 1+ iterations. For the bound on the size of the communities, note that by Observation 5, / ≤ . Hence, each of the removed edges satisfy | ( )| ≤ (3 + ) / ≤ (3 + ) . □ The results for the community degeneracy in Table 1 follow from Theorem 4.3 by using either the sequential greedy preprocessing, Lemma 4.4, or by using a hybrid approach similar to Section 4.2.

CONCLUSION AND FUTURE WORK
We presented work improvements over previous algorithms onclique listing in -degenerate and -community-degenerate graphs. The improvements are exponential in the clique size , in particular when = Θ(  Table 2: Overview over the selected graphs. is the degeneracy; denotes the triangles in the graph. All graphs are publicly available [35,46] and have been symmetrized.

B EXPERIMENTAL EVALUATION
In this section, we present an empirical evaluation of Algorithm 1.
For all experiments, we use the (exact) degeneracy order from Section 4.1. We compare our implementation with the state-of-theart implementations by Danisch et al. [25] and Shi et al. [49].

B.1 Data Set
We assembled a set of graphs to test the different implementations. These graphs represent different fields of applications and exhibit different structural properties [13]. Table 2 provides a brief overview of the graphs. The graphs 'Tech-as-skitter', 'Ca-DBLP-2012' and 'Orkut' have already been used previously for benchmarking by Danisch et al. [25] and Shi et al. [49]. Orkut is a relatively large online social network, Ca-DBLP-2012 is the collaboration network of the DBLP 2012, and Tech-as-Skitter is an internet topology graph, generated in 2005 by daily traceroutes [35]. In addition, we added some non-standard graphs to the set: 'Gearbox', 'Chebyshev4', 'Bio-SC-HT' and 'Jester2'. Gearbox is a structural network from an aircraft flap actuator. Chebyshev4 is a structural network as well. It is derived from a 4th order Chebyshev scheme for numerical integration. Jester2 is a joke-rating network, and Bio-SC-HT is a network derived from functional gene associations [46].

B.2 Experimental Setup
The bulk of our experiments was performed on the Piz Daint Computing platform by CSCS. We used the XC40 Multicore Compute nodes, equipped with two Intel ® Xeon ® E5-2695 v4 2.10GHz, 18 cores/36 threads, 45MB of Intel ® Smart Cache and each with 64/128 GB RAM [24,26].
The code was compiled in both instances with GCC 8.3 with the optimization flags -O3 and -march=native. Piz Daint supports AVX2. GCC 8.3 supports OpenMP 4.5 [32], which was chosen for parallel programming.
All measurements were repeated at least 10 times, except for the runs for Orkut and Jester with ≥ 7, which were repeated 5 times  Figure 7: Results on the Chebyshev4 graph.
due to the long running times. The reported times are arithmetic averages over all measurements.

B.3 Results
See Figure 7, Figure 8 and Figure 9 for the comparison of our algorithm (c3List) with Shi et al. (ArbCount [49]) and Danisch et al.
(kcList [25]). We report the runtime for 72 threads and vary the clique size from 6 to 10. The empirical standard deviation of the runtimes is less than 5.2% for clique sizes ≥ 8 for all algorithms and all graphs except the Gearbox graphs (which can be solved quickly). For Gearbox graphs with = 10, the standard deviation is less than 6.4%. Other results need to be interpreted with care, as the standard deviation is larger than 10% for at least one graph and algorithm.
For small clique sizes ( < 8), it depends on the graph which algorithm is fastest. These results also have a higher variance.
For larger clique sizes ( ≥ 8), Shi et al. [49] generally outperform Danisch et al. [25]. Our community-centric algorithm is faster than both on a majority of the instances starting at = 8. The advantage of our implementation over the others generally grows with the clique size. This trend might be because of the non-constant base to the exponent in the work bounds of our algorithm.
Overall, for cliques of size ≥ 9, our algorithm is slower in one instance (Orkut) and outperforms the others by 3.4 − 37.9%. Our algorithm appears to be relatively better when there are few triangles per vertex. For those graphs (Tech-As-Skitter, Gearbox, CA-DBLP-2012), our algorithm is 16.5 − 37.9% and 13.8 − 33.7% faster than the next fastest implementation for cliques of size 9 and 10, respectively. The good performance on those graphs could be because our pruning technique is particularly effective when there are fewer triangles.  Figure 9: Runtime Results for 72 threads for varying clique sizes. Our algorithm is c3List, ArbCount is by Shi et al. [49], and kcList is by Danisch et al. [25]