{'fraction_non_alphanumeric': 0.04757765221170885, 'fraction_numerical': 0.01746408550380599, 'mean_word_length': 4.149678604224059, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 32, 'https://': 1, '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 Batch-Dynamic k-Core Decomposition

Maintaining a k-core decomposition quickly in a dynamic graph is an important problem in many applications, including social network analytics, graph visualization, centrality measure computations, and community detection algorithms. The main challenge for designing efficient k-core decomposition algorithms is that a single change to the graph can cause the decomposition to change significantly. We present the first parallel batch-dynamic algorithm for maintaining an approximate k-core decomposition that is efficient in both theory and practice. Given an initial graph withm edges, and a batch of B updates, our algorithmmaintains a (2+δ)-approximation of the coreness values for all vertices (for any constant δ > 0) in O (B log2m) amortized work and O (log2m log logm) depth (parallel time) with high probability. Our algorithm also maintains a low out-degree orientation of the graph in the same bounds. We implemented and experimentally evaluated our algorithm on a 30-core machine with two-way hyper-threading on 11 graphs of varying densities and sizes. Compared to the state-of-the-art algorithms, our algorithm achieves up to a 114.52x speedup against the best multicore implementation and up to a 497.63x speedup against the best sequential algorithm, obtaining results for graphs that are orders-of-magnitude larger than those used in previous studies. In addition, we present the first approximate static k-core algorithm with linear work and polylogarithmic depth. We show that on a 30-core machine with two-way hyper-threading, our implementation achieves up to a 3.9x speedup in the static case over the previous state-of-the-art parallel algorithm. Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/qqliu/batch-dynamic-kcore-decomposition/.


Introduction
Discovering the structure of large-scale networks is a fundamental problem for many areas of computing, including social network analysis, computational biology, and spam and fraud detection, among many others. One of the key challenges is to detect communicaties in which individuals (or vertices) have close ties with one another, and also to understand how well-connected a particular individual is to the community. For example, a social network provider may need this information to determine how many friends of a user needs to drop out before that user also leaves. The well-connectedness of a node or a group of nodes is naturally captured by the concept of a -core or, more generally, the -core decomposition; hence, this particular problem and its variants have been widely studied in the past and also more recently in the machine learning [2,25,27], database [11,15,23,45,52], graph analytics [19,20,38,40], and other communities [26,41,49,60].
Given an undirected graph , with vertices and edges, the -core of the graph is the maximal subgraph ⊆ such that the induced degree of every vertex in is at least . The -core decomposition of the graph is defined as a partition of the graph into layers such that a vertex is in layer if it belongs to a -core but not a ( + 1)-core, which induces a natural hierarchical clustering on the input graph. Many well-known algorithms for -core decomposition are inherently sequential. The classic algorithm for finding such a decomposition is to iteratively select and remove all vertices with smallest degree from the graph until the graph is empty. Unfortunately, the length of the sequential dependencies (the depth) of such a process can be Ω( ) given a graph with vertices. Due to the potentially large depth, this algorithm cannot fully take advantage of parallelism on modern machines, and can therefore be too costly to run on large graphs. As -core decomposition is a P-complete problem [4], it is unlikely that there is a parallel algorithm with polylogarithmic depth for this problem. To obtain parallel methods for this problem, we relax the condition of obtaining an exact -core decomposition to one of obtaining a close approximate -core decomposition. Parallel Static Approximate -core. In this paper, we present a novel parallel static approximate -core decomposition algorithm based on a relaxed version of the peeling algorithm of [19] that achieves both optimal linear work and has polylogarithmic depth. In contrast to existing parallel approximate -core algorithms [25,27] which are designed for distributed memory, our algorithm is designed for shared-memory multicore machines, which have been shown to be able to process the largest graphs with hundreds of billions of edges efficiently [20,51]. To the best of our knowledge, ours is the first parallel algorithm to achieve work-efficiency and polylogarithmic depth. Our bounds are summarized in Theorem 1.1.
Theorem 1.1. For a graph with edges, 1 for any constant > 0, there is an algorithm that finds an (2 + )-approximate -core decomposition in ( ) expected work and (log 3 ) depth with high probability, 2 using ( ) space.
Parallel Batch-Dynamic Approximate -core. Because of the rapidly changing nature of today's graphs, it is inefficient to recompute the -core decomposition of the graph from scratch on every update. For this purpose, dynamic -core decompositions are especially useful. In this paper, we design an approximate -core algorithm with strong theoretical guarantees for the batch-dynamic setting, where updates to the graph are provided in batches that can be processed in parallel. Our batch-dynamic algorithm efficiently maintains the -core decomposition in parallel given batches of updates, and uses a level data structure inspired by [8,33] to maintain a partition of the vertices satisfying certain degree properties. Our algorithm takes (log 2 ) amortized work per update, matching the best sequential algorithm [69], while achieving polylogarithmic depth at the same time. The bounds for our algorithms are as follows.
Theorem 1.2. Provided an input graph with edges, and a batch of updates B, our algorithm maintains a (2 + )-approximation of the coreness values for all vertices (for any constant > 0) in (|B| log 2 ) amortized work and (log 2 log log ) depth with high probability, using ( log 2 + ) space.
Moreover, our parallel batch-dynamic algorithm can be used to maintain low out-degree orientations and approximate densest subgraphs in the same complexity bounds. Experimental Evaluation. In addition to our theoretical contributions, we also provide optimized multicore implementations of both our static and batch-dynamic algorithms. We compare the performance of our algorithms with state-of-the-art algorithms on a variety of real-world graphs using a 30-core machine with two-way hyper-threading. Our parallel static approximate -core algorithm achieves a 2.8-3.9x speedup over the fastest parallel exact -core algorithm [19], and achieves a 14.76-36.07x self-relative speedup. We show that our parallel batch-dynamic -core algorithm achieves up to a 497.63x speedup over the state-of-the-art sequential dynamic -core algorithm [69], while achieving comparable accuracy. Furthermore, our batch-dynamic algorithm is able to outperform our static approximate -core algorithm by up to 75.94x on small batch sizes. We also achieve up to a 114.52x speedup over the state-of-the-art parallel batch-dynamic -core algorithm of Hua et al. [34]. Related Work. The -core decomposition of a graph and its related concepts of arboricity, low out-degree orientation, and densest subgraph are widely used in machine learning applications, including community detection [7,54], analyzing social network dynamics [9], visualizing large-scale complex networks [2], analyzing protein networks [3], approximating network centrality measures [32], and many more. In addition, low out-degree orientations can lead to efficient graph algorithms for sparse graphs [56,68].
Many parallel -core algorithms have been designed for the static setting (e.g., [17,19,21,38,53,55,57,71]). The algorithms of [25,27] are approximate algorithms that achieve a logarithmic or sub-logarithmic number of rounds in the distributed MPC model. However, the local computation in their algorithms is free in the MPC model, but have linear depth in the shared-memory setting, which is worse than the polylogarithmic depth bound that we achieve. [25,27] do not report running times in their paper, and hence it is difficult to compare actual performance. We note that we are able to process graphs used in their papers using a single commodity multicore machine.
There has been significant interest in obtaining fast and practical dynamic -core algorithms. Dynamic algorithms have been developed for both the sequential [46,46,47,59,69,75,77] and parallel [5,34,37] settings. However, to the best of our knowledge, there are no parallel dynamic -core algorithms with polylogarithmic depth, which our algorithm achieves. Several dynamic algorithms have also been developed for the closely-related -truss problem [1,35,50,76].
A recent paper by Sun et. al. [69] provides a sequential, dynamic -core decomposition algorithm that gives a (4 + )-approximation in poly log time. Their algorithm is inherently sequential and parallelizing their algorithm requires non-trivial changes in theory and in practice. The most recent, state-of-the-art parallel batchdynamic algorithm by Hua et al. [34] relies on the concept of a joint edge set whose insertion and removal determines the core numbers of the nodes; however, their algorithm does not achieve polylogarithmic depth.
Related dynamic problems to -core decompositions have been recently studied in the theory community [8,33,68]. Such problems include densest subgraph [8,64] and low out-degree orientations [33,68]. None of these aforementioned works proved guarantees regarding the -core decomposition that can be maintained via a level data structure. Furthermore, no prior work have provided implementations of their structures or performed experiments on the practical efficiency of these structures.

Preliminaries
Graph Definitions. For an unweighted, undirected graph = ( , ) where is the set of vertices and is the set of edges, let = | |, the number of vertices, and = | |, the number of edges. We denote the set of neighbors of vertex as ( ). For a subset of vertices, ⊆ , ( ) = ∈ ( ). The arboricity, , of is the minimum number of forests into which can be partitioned, and is upper bounded by ( √ ) [14].
Definition 2.1 (Low Out-degree Orientation). A low out-degree orientation of an undirected graph is an orientation of its edges such that the out-degree of every vertex is ( ).
The -core of a graph is the maximal subgraph of such that the induced degree of every vertex in is at least . Definition 2.2 ( -Core Decomposition). A -core decomposition is a partition of vertices into layers such that a vertex is in layer if it belongs to a -core but not to a ( + 1)-core. ( ) denotes the layer that vertex is in, and is called the coreness of .
The above defines an exact -core decomposition. Aapproximate -core decomposition is defined as follows.
The level data structure also provides guarantees on the approximation of the densest subgraph in the input graph. Model Definitions. We analyze the theoretical efficiency of our parallel algorithms in the work-depth model. The work-depth model is a fundamental tool in analyzing parallel algorithms, e.g., see [10,20,30,70,74] for a sample of recent practical uses of this model. The work-depth model is defined in terms of two complexity measures work and depth, which are standard measures for analyzing shared-memory algorithms [16,36]. The work of an algorithm is the total number of operations executed by the algorithm. The depth is the longest chain of sequential dependencies in the algorithm. We assume that concurrent reads and writes are supported in (1) work/depth. A work-efficient parallel algorithm is one with work that asymptotically matches the best-known sequential time complexity for the problem. We use a parallel reduce-add in our algorithms, which takes as input a sequence of length , and returns the sum of the entries in using ( ) work and (log ) depth [36].
Our parallel algorithms operate in the batch-dynamic setting. A batch-dynamic algorithm processes updates (vertex or edge insertions/deletions) in batches of size B. For simplicity, since we can reprocess the graph using an efficient parallel static algorithm when |B| ≥ , we consider 1 ≤ |B| < for our bounds.
Problem Definition. Given a graph = ( , ) and a sequence of batches of edge insertions and deletions, B 1 , . . . , B , where B = ( delete , insert ), the goal is to efficiently maintain a (1 + )approximate -core decomposition (for any constant > 0) after applying each batch B (in order) on . In other words, let = ( , ) be the graph after applying batches B 1 , . . . , B and suppose we have a (1 + )-approximate -core decomposition on ; then, for B +1 , our goal is to efficiently find a (1 + )-approximate -core decomposition of +1 = , ( ∪ +1 insert ) \ +1 delete . All notations used in our paper are summarized in Table 1. 3 Batch-Dynamic (2 + )-Approximate -Core Decomposition In this section, we describe our parallel, batch-dynamic algorithm for maintaining an (2 + )-approximate -core decomposition (for any constant > 0) and prove its theoretical efficiency.

Algorithm Overview
We provide a parallel level data structure (PLDS) that maintains a (2 + )-approximate -core decomposition and low out-degree orientation that builds off the sequential level data structures (LDS) of [8,33]. Our algorithm achieves (log 2 ) amortized work per update and (log 2 log log ) depth whp. We also present a deterministic version of our algorithm that achieves the same work bound with (log 3 ) depth. Our data structure can also handle batches of vertex insertions/deletions, which we discuss in Section 3.4.  As in the case of [33], our data structure can handle changing arboricity that is not known a priori to the algorithm. This means that our data structure can handle the case when the arboricity of the underlying graph changes throughout the execution of batches of updates and successfully maintains approximations of the coreness of each node with respect to the current arboricity.
The level data structure consists of a partition of the vertices of the graph into = (log 2 ) levels. 3 The levels are partitioned into equal-sized groups of consecutive levels. Vertices move up and down levels depending on the type of edge update incident to the vertex. Rules governing the induced degrees of vertices to neighbors in different levels determine whether a vertex moves up or down. Using information about the assigned level of a vertex, we obtain a (2 + )-approximation on the coreness of the vertex. Fig. 2 shows an illustration of this data structure. There are Θ(log ) groups, each with Θ(log ) levels (labeled on the right).
Each vertex is in exactly one level of the structure and moves up and down by some movement rules. We describe our parallel level data structure in more detail in Section 3.3.

Low Out-Degree Orientations and LDS
Low out-degree orientations have been used in many efficient static and dynamic algorithms for graphs (e.g., [6,22,29,68]). Our work is based on the sequential level data structures (LDS) of [8,33], which maintain a low out-degree orientation under dynamic updates. Within their LDS, a vertex moves up or down levels one by one, meaning that a vertex (incident to an edge update) first checks whether an invariant is violated, and then may move up or down one level. Then, the vertex checks the invariants and repeats.
Unfortunately, such a procedure can be slow in practice. Specifically, a vertex that moves one level could cause a cascade of vertices to move one level (illustrated in Example 3.1). Then, if the vertex moves again, the same cascade of movements may occur.
Example 3.1. In Fig. 3, suppose a vertex at level 1 is incident to an edge deletion ( , ) (dashed edge in red) and must move down one level. This in turn could cause another one of its neighbors at level 2 to move down one level, leading to a cascade of vertices which must move down ( at level 3, then at level 4, etc.). If could move down one additional level, it may cause another cascade of movements.
Furthermore, any trivial parallelization of the LDS to support a batch of updates will run into race conditions and other issues, requiring the use of locks which blows up the runtime in practice. We must also be careful not to perform unnecessary work; one example is a vertex that moves up due to edge insertions but then later moves down due to edge deletions (from the same batch).
Thus, our PLDS algorithm solves several challenges posed by the sequential algorithm. Provided a batch B of edge insertions and deletions: (1) our algorithm processes the levels in a careful order that yields provably low depth for batches of updates; (2) our algorithm processes insertions and deletions in separate batches to avoid excess work; (3) our insertion algorithm processes vertices on each level at most once, which is key to bounding the depth-after a vertex moves up from level ℓ, no future step in the algorithm requires a vertex to move up from level ℓ; and (4) our deletion algorithm moves vertices to their final level in one step. In other words, a vertex moves at most once in a batch of deletions before a new batch arrives.

Detailed PLDS Algorithm
As mentioned previously, the vertices of the input graph = ( , ) are partitioned across levels. For each level ℓ = 0, . . . , − 1, let ℓ be the set of vertices that are currently assigned to level ℓ. Let ℓ be the set of vertices in levels ≥ ℓ. Provided a constant > 0, the levels are partitioned into groups 0 , . . . , ⌈log (1+ ) ⌉ , where each group contains ⌈log (1+ ) ⌉ consecutive levels. Each ℓ ∈ ⌈log (1+ ) ⌉, ( + 1) ⌈log (1+ ) ⌉ − 1 is a level in group . Our data structure consists of = (log 2 ) levels. The PLDS satisfies the following invariants, which also govern how the data structure is maintained. The invariants assume a given constant > 0 and a constant > 0. 4 The below invariants follow invariants defined in [8,33].
All vertices with no neighbors are placed in level 0. An example partitioning of vertices and the maintained invariants is shown in Example 3.2.
Let ℓ ( ) be the level that is currently on. We define the group number, ( ), of a vertex to be the index of the group where ℓ ( ) ∈ . Similarly, we define (ℓ) = to be the group number for level ℓ where ℓ ∈ . We define the up-degree, up( ), of a vertex to be the number of its neighbors in ℓ ( ) (up-neighbors), and up*-degree, up * ( ), to be the number of its neighbors in ℓ ( )−1 (up * -neighbors). These two notions of induced degree correspond to the requirements of the two invariants that our data structure maintains. Lastly, the desire-level dl( ) of a vertex is the closest level to the current level of the vertex that satisfies both Invariant 1 and Invariant 2. We show that the invariants above are always maintained except for a period of time when processing a new batch of insertions/deletions. During this period, the data structure undergoes a rebalance procedure, during which the invariants may be violated. The main update procedure is shown in Algorithm 1. It separates the updates into insertions and deletions (Line 1), and then calls RebalanceInsertions (Line 2: Algorithm 2) and RebalanceDeletions (Line 3: Algorithm 3). We make note of two crucial observations that we prove in the analysis: when processing a batch of insertions, Invariant 2 is never violated; and similarly, when processing a batch of deletions, Invariant 1 is not violated. This means that no vertex needs to move down when processing a batch of insertions and no vertex needs to move up when processing a batch of deletions. We first describe the data structures that we maintain and Insert into the graph. Mark and move to level + 1 and create [ ] to store 's neighbors at level . 8: parfor each ∈ ( ) of a vertex that moved to level + 1 and stayed in level do   parfor each ∈ ( ) of a vertex that moved to level + 1 and is in level ℓ ( ) ≥ + 2 do  then the RebalanceInsertions and RebalanceDeletions procedures below. Data Structures. Each vertex keeps track of its set of neighbors in two structures. keeps track of the neighbors at 's level and above. We denote this set of 's neighbors by [ ]. keeps track of neighbors of for every level below ℓ ( )-in particular, [ ] contains the neighbors of at level < ℓ ( ). We describe specific data structure implementation details in Section 3.6 and Appendix A. RebalanceInsertions( ins ). Algorithm 2 shows the pseudocode. Provided a batch of insertions ins , we iterate through the levels from the lowest level ℓ = 0 to the highest level ℓ = −1 (Algorithm 2, Line 5). For each level, in parallel we check the vertices incident to edge insertions in ins (or is marked) to see if they violate Invariant 1 (Line 6). If a vertex in the current level violates Invariant 1, we move to level + 1 (Line 7). After moving , we update structures [ ], , and the structures of ∈ ( ) where ℓ ( ) ∈ [ , + 1]. First, we create [ ] to store the neighbors of in level (Line 7). If moved to level + 1 and stayed in level , then we delete from [ ] and instead insert into [ ] (Line 9). We do not need to make any data structure modifications for since stays in [ ].
Similarly, no data structure modifications to and are necessary when both and move to level +1. For each neighbor of on level + 1, we need to check whether it now violates Invariant 1. If it does, then we mark the vertex (Line 11). We process any such marked vertices when we process level + 1. We also update the and arrays of every neighbor of on level + 1 (Line 12 Remove from the graph. 5: parfor each vertex where up * ( ) < (1 + ) (ℓ ( ) −1) do 6: Calculate dl( ) using CalculateDesireLevel( ). 7: for each level ∈ [0, − 1] starting with level = 0 do 8: parfor each vertex where dl( ) = do 9: Move to level . 10: parfor each neighbor of a vertex that moved to level where ℓ ( ) ≥ ℓ ( ) do 11: Let and be the previous levels of and , respectively, before the move. 12: if up * ( ) < (1 + ) (ℓ ( ) −1) then 23: Recalculate dl( ) using Algorithm 4.
We conclude by making appropriate modifications to for each neighbor on levels ≥ + 2 (Line 13-Line 14). Specifically, let be one such neighbor, we remove from [ ] and add to [ + 1]. All neighbors of vertices that moved can be checked and processed in parallel. Finally, becomes unmarked if it satisfies all invariants; otherwise, it remains marked and must move again in a future step (Line 15). A detailed example of this procedure is below.
Example 3.4. Fig. 4 shows an example of our entire insertion procedure described in Algorithm 2. The red lines in the example represent the batch of edge insertions. Thus, in ( ), the newly inserted edges are the edges ( , ), ( , ), and ( , ). We iterate from the bottommost level (starting with level 0) to the topmost level (level − 1).
The first level where we encounter vertices that are marked or are adjacent to an edge insertion is level 2. Since level 2 is part of group 0, the cutoff for Invariant 1 is (2 + 3/ )(1 + ) 0 = 3 provided = 3 and = 0.4. In level 2, only violates Invariant 1 since the number of its neighbors on levels ≥ 2 is 4 ( , , , and ), so up( ) = 4 > 3 (shown in ( )). Then, in ( ), we move up to level 3. We need to update the data structures for neighbors of at level 3 and above (as well as 's own data structures); the vertices with data structure updates are , , , and . After the move, becomes marked because it now violates Invariant 1 (the cutoff for level 3 is 3 · (1.4) = 4.2 since level 3 is in group 1); becomes unmarked because it no longer violates Invariant 1.
In ( ), we move on to process level 3. The only vertex that is marked or violates Invariant 1 is . Therefore, we move up one level (shown in ( )) and update relevant data structures (of , , , , and ). RebalanceDeletions( del ). Deletions are handled in a similar way to insertions, except for one major difference. Instead of moving vertices down one level at a time, we ensure that when we move a vertex, we move it to its final level (i.e., we will not move this vertex again during this procedure). As we show in the analysis, this guarantee is crucial to obtaining low depth. Algorithm 3 shows the pseudocode. For each vertex incident to an edge deletion, first we check whether it violates Invariant 2 (Algorithm 3, Line 5). In Line 5, (ℓ ( ) −1) gives the group number where ℓ ( ) −1 ∈ . If it violates Invariant 2, we calculate its desirelevel, dl( ), using CalculateDesireLevel (Algorithm 3, Line 6). We describe how to do this at the end of this subsection. As in the insertion procedure, we iterate through the levels from = 0 to = − 1 (Line 7). Then, in parallel for each vertex whose desirelevel is , we move the vertex to level (Line 8-Line 9). As with insertions, we update the data structures of and ∈ ( ) where ℓ ( ) ≥ (Line 10-Line 21). Finally, we update the desire-level of neighbors of that no longer satisfy Invariant 2 (Line 22-Line 23). We process all vertices that move as well as their neighbors in parallel.
An example of the RebalanceDeletions procedure is given below. Example 3.5. Fig. 5 shows an example of our entire deletion procedure described in Algorithm 3 for = 1 and = 3. The red dotted lines in the example represent the batch of edge deletions. Thus, in ( ), the newly deleted edges are the edges ( , ) and ( , ). For each vertex adjacent to an edge deletion, we calculate its desirelevel, or the closest level to its current level that satisfies Invariant 2.
In this example, shown in ( ), only and violate Invariant 2. The lower bound on the number of neighbors that must be at or above level 3 for and level 4 for is (1 + ) 1 = 2 since = 1 and levels 3 and 4 are in group 1. (Recall that the lower bound is calculated with respect to the level below and .) We calculated that the desire levels of and are both 3. The desire levels of and are their current levels because they do not violate the invariant. Then, we iterate from the bottommost level (starting with level 0) to the topmost level (level − 1). Level 3 is the first level where vertices want to move. Then, we move and to level 3 (shown in ( )). We only need to update the data structures of neighbors at or above and so we only update the data structures of , , and . Invariant 2 is no longer violated for and . In fact, our algorithm guarantees that each vertex moves at most once. We check whether any of or 's up-neighbors violate Invariant 2. Indeed, in this example, now violates the invariant. We recompute the desire-level of and its desire-level is now 4 (shown in ( )). We proceed to process level 4 and move to that level (shown in ( )). CalculateDesireLevel( ). Algorithm 4 shows the procedure for calculating the desire-level, dl( ), of vertex , which is used in Algorithm 3. Let (ℓ) be the index where level ℓ ∈ . We use a
doubling procedure followed by a binary search to calculate our desire-level. We initialize a variable to up * ( ) (number of neighbors at or above ℓ ( ) − 1). Starting with level ℓ ( ) − 2, we add the number of neighbors in level ℓ ( ) −2 to (Algorithm 4, Line 3). This procedure checks whether moving to ℓ ( ) − 1 satisfies Invariant 2 (Line 4). If it passes the check, then we are done and we move to ℓ ( ) − 1. Otherwise, we double the number of levels from which we count neighbors (Line 6). In our example, in the next iteration, we sum the number of neighbors in levels [ℓ ( ) − 4, ℓ ( ) − 3]. We continue until we find a level where Invariant 2 is satisfied. Let this level be ℓ ′ and the previous cutoff be ℓ prev . Finally, we perform a binary search within the range [ℓ ′ , ℓ prev ] to find the closest level to ℓ ( ) that satisfies Invariant 2 (Line 5). The sum on Line 3 is done using a parallel reduce.

Vertex Insertions and Deletions
We can handle vertex insertions and deletions by inserting vertices which have zero degree and considering deletions of vertices to be a batch of edge deletions of all edges adjacent to the deleted vertex. When we insert a vertex with zero degree, it automatically gets added to level 0 and remains in level 0 until edges incident to the vertex are inserted. For a vertex deletion, we add all edges incident to the deleted vertex to a batch of edge deletions. Note, first, that all vertices which have 0 degree will remain in level 0. Thus, there are at most ( ) vertices which have non-zero degree.
Because we have (log 2 ) levels in our data structure, we rebuild the data structure once we have made 2 edge updates (including edge updates from edges incident to deleted vertices). Rebuilding the data structure requires ( log 2 ) total work which we can amortize to the 2 edge updates to (log 2 ) amortized work. Running Algorithm 2 and Algorithm 3 on the entire set of ( ) edges requires˜(log 2 ) depth.

Coreness and Low-Outdegree Orientation
To obtain the coreness estimates from our PLDS, we only need to maintain the current level of each vertex and the number of levels in a group (recall that all groups have equal numbers of levels). Then, we calculate the estimate of the coreness of to beˆ( ) = (1 + ) max( ⌊ℓ ( )/ ⌈log 1+ ⌉ ⌋−1,0) , where the number of levels in a group is ⌈log 1+ ⌉. In other words, our estimate of the coreness of is (1 + ) , where is the group index of the highest level that is the last level in a group and is equal to or lower than ℓ ( ). We need to perform this calculation in order to obtain our optimum approximation ratios both in theory (Lemma 3.16) and in practice. To see an example, consider vertex in Fig. 5 ( ). We estimateˆ( ) = 1 since the highest level that is the last level of a group and is equal to or below level ℓ ( ) = 4 is level 2. Level 2 is part of group 0 so our coreness estimate for is (1 + ) 0 = 1. This is a 2-approximation of its actual coreness 2.
To obtain a low-outdegree orientation we maintain an orientation of each edge from the endpoint at a lower level to the endpoint with a higher level. So edges are directed from lower to higher levels. For any two vertices on the same level, we direct the edge from the vertex with higher ID to the vertex with lower ID. Performing this procedure results in an 8 outdegree orientation, where is the arboricity of the graph.

Data Structure Implementations
Due to space constraints, we only specify the data structures used to obtain our randomized (high probability) bounds. We implement these data structures in our experiments. Our data structures presented here result in ( log 2 + ) space usage. However, we present two additional sets of data structures in Appendix A: one that achieves ( ) space with an (log 2 ) factor increase in depth and another that results in a deterministic PLDS.
Our data structure uses parallel hash tables, which support concurrent insertions, deletions, or finds in ( ) amortized work and (log * ) depth whp [28]. We use dynamic arrays, which support adding or deleting elements from the end in ( ) amortized work and (1) depth.
We first assign each vertex a unique ID in [ ]. We also maintain an array of size keyed by vertex ID that returns a parallel hash table containing neighbors of on levels ≥ ℓ ( ). For each vertex , we maintain a dynamic array keyed by indices ∈ [0, ℓ ( ) − 1]. The 'th entry of the array contains a pointer to a parallel hash table containing the neighbors of in level . Appropriate pointers exist that allow (1) work to access elements in structures. Furthermore, we maintain a hash table which contains pointers to vertices where dl( ) ≠ ℓ ( ), partitioned by their levels. This allows us to quickly determine which vertices to move up (in Algorithm 2) or move down (in Algorithm 3).

Analysis
We now present the lemmas used to analyze our algorithms, as well as our overall bounds and approximation guarantee. Depth and Work Bound. First, it is easy to show that there exists a level where both invariants are satisfied. This allows our PLDS data structure to assign each vertex to a single level. Proof. First note that no vertex can simultaneously violate both Invariant 1 and Invariant 2. Thus, suppose first that violates Invariant 1. Then, this means that the number of neighbors of on levels ≥ ℓ ( ) is more than (2 + 3/ ) (1 + ) ( ) where ( ) is the group number of . If still violates Invariant 1 on level ℓ ( ) + 1, then we keep moving to the next level.
Otherwise, does not violate Invariant 1 on level ℓ ( ) + 1. Since we know that violated Invariant 1 on level ℓ ( ), then after we move to ℓ ( ) + 1, 's up*-degree is greater than (1 + ) (ℓ ( )) ; hence, also does not violate Invariant 2. The very last level of the levels has up-degree bound  Proof. The first part of the algorithm inserts the edges into the data structure. Since no edges are removed from the data structures, the degrees of all the vertices after the insertion of edges cannot decrease. Invariant 2 was satisfied before the insertion of the edges, and hence, it remains satisfied after the insertion of edges because no vertices lose neighbors. We prove that the lemma holds for the remaining part of Algorithm 2 via induction on the level processed by the procedure. In the base case, when = 0, all vertices in the level which violate Invariant 1 are moved up to a level dl( ) > 0. By definition of desire-level, is moved to a level where Invariant 2 is still satisfied, by Lemma 3.6. Vertices from level 0 which move to levels ≥ 1 cannot decrease the up*-degree for neighbors in all levels where > 1. Thus, Invariant 2 cannot be violated for these vertices. Vertices not adjacent to are not affected by the move.
We assume that Invariant 2 was not violated up to level and prove it is not violated while processing vertices on level + 1. By our induction hypothesis, no vertices violate Invariant 2 before we process level +1. Then, when we process level +1, no vertices move down to a lower level than + 1 by construction of our algorithm because Invariant 2 is not violated for any vertex on level + 1 and if Invariant 1 is violated for any vertex , must move up to a higher level. Any vertex which moves up to a higher level cannot decrease the up*-degree of neighbors of . Hence, no vertex on levels ≥ + 1 can violate Invariant 2. The up*-degree of vertices on levels < + 1 are not affected by the move. Hence, no vertices on levels < + 1 violate Invariant 2. Finally, if a vertex on level + 1 violates Invariant 1, it will move to a level > + 1 where both invariants are satisfied by Lemma 3.6. □ Proof. Algorithm 3 first applies all the edge deletions in the batch. Edge deletions cannot make the up-degree of any vertex greater; thus, no vertex violates Invariant 1 after applying the edge deletions. We prove that the rest of the algorithm does not violate Invariant 1 via induction over the levels . Specifically, we use as our induction hypothesis that after processing the 'th level, no vertices violate Invariant 1. In the base case, when = 0, no vertices violate Invariant 1 at the beginning, and vertices from levels > 0 move to level 0. This means that during the processing of level = 0, vertices only move to level 0 from a higher level. Thus, all such vertices that move will move to a lower level. Since vertices which move to lower levels do not increase the up-degree of any other vertices, no vertex can violate Invariant 1 at the end of processing level 0. We now prove the case for processing level + 1. In this case, we assume by our induction hypothesis that no vertices violate Invariant 1 after we finish processing level . Thus, all vertices that want to move to level + 1 and violate Invariant 2 are at levels > + 1. Such vertices move down and thus cannot increase the up-degree of any vertex. This means that after moving all vertices that want to move to level + 1, no vertices violate Invariant 1. □ Batch Insertion Depth Bound. The depth of our batch insertion algorithm (Algorithm 2) depends on the following lemma which states that once we have processed a level (after finishing the corresponding iteration of Line 5), no vertex will want to move from any level lower than that level. This means that each level is processed exactly once, resulting in at most (log 2 ) levels to be processed sequentially.
Proof. We prove this via induction. For the base case = 0, all vertices on level 0 are part of each other's up-degree; then, no vertices which move up from = 0 can cause the up-degree of any vertices remaining in level 0 to increase. We now assume the induction hypothesis for − 1 and prove the case for . Vertices on level ≤ already contain vertices on levels ≥ in its updegree. Such vertices on levels ≥ when moved to a higher level are still part of the up-degree of vertices on levels ≤ . Hence, no vertices on levels ≤ will violate Invariant 1 due to vertices in levels ≥ moving up to a level > . Then, in order for a vertex with ℓ ( ) > to have dl( ) ≤ , some neighbors of must have moved to a level ≤ . By Lemma 3.7, no vertices move down during Algorithm 2, so this is not possible. □ Batch Deletion Depth Bound. For the batch deletion algorithm (Algorithm 3), we prove that after all vertices which have dl( ) = are moved to the 'th level, no vertex will have dl( ) ≤ . As in the insertion case, this means that each level is processed exactly once, resulting in at most (log 2 ) levels to be processed sequentially.
Lemma 3.10. After processing all vertices that move to level in Algorithm 3, no vertex needs to be moved to any level ≤ in a future iteration of Line 7; in other words, no vertex has dl( ) ≤ after level has been processed.
Proof. We prove this invariant via induction. In the base case when = 0, all vertices with dl( ) = 0 are moved to level 0. All vertices which have dl( ) = 0 are vertices which have degree 0. Thus, all vertices that do not have dl( ) = 0 have degree ≥ 1 and have dl( ) ≥ 1. Hence, after moving all vertices with dl( ) = 0 to level 0, no additional vertices need to be moved to level 0. Assuming our induction hypothesis, we now show our lemma holds for level + 1. All vertices that move to level + 1 violated Invariant 2 and hence have up*-degree < (1 + ) ( −1) at level > + 1 and up*degree ≥ (1 + ) ( ) at level + 1. After moving all vertices with dl( ) = + 1 to level + 1, no vertices on levels ≤ + 1 have their up*-degree decreased by the move. We conclude the proof with vertices at levels > + 1. Suppose for the sake of contradiction that there exists some vertex on level > + 1 which has dl( ) ≤ + 1 after the move. In order for dl( ) ≤ + 1, some neighbor(s) of must move below level , a contradiction. Finally, due to Lemma 3.8, no vertices below level + 1 will move up. □ The depth of our algorithm follows almost immediately from the above lemmas. Before we present the final lemmas for the depth of our algorithm, we discuss the depth incurred from our data structures and also briefly the deterministic and space-efficient settings.
Deterministic Setting In the deterministic setting, we maintain the list of neighbors using dynamic arrays, which also means that we maintain and access the sizes of these arrays in (1) work and depth. Because we are using dynamic arrays, we need to occasionally resize the arrays in (1) amortized work and (1) depth. Finally, we can modify the arrays in (1) work and depth (not counting the depth for resizing).
Randomized Setting In the randomized setting, we maintain the list of neighbors using parallel hash tables keyed by level. Each vertex has one hash table which contains their neighbors at each level below them as well as all its neighbors at the same or higher levels. Then, vertices themselves are contained in separate hash tables for each level. Parallel lookups into the hash tables each require (1) work and depth, whp. Then, modifying (inserting and deleting) elements within the hash tables require (log log ) depth and work proportional to the number of inserted elements, whp.
Space-Efficient Setting In the space-efficient setting, we replace the structure used to represent with a linked list. Inserting and deleting nodes from the linked list requires (1) work and depth (assuming we are given a pointer to the node). Then, resizing the dynamic arrays (pointed to by the linked lists to maintain the set of elements in each level) require (1) amortized work and (1) depth.
The only additional depth we need to consider is the depth acquired from Algorithm 4. Both the doubling search and the binary search require (log ) = (log log ) depth. All other depth comes from concurrently modifying and accessing dynamic arrays and hash tables, which can be done in (log * ) depth whp.
Using the above, we prove the depth of Algorithm 1.
Lemma 3.11. Algorithm 1 returns a deterministic level data structure that maintains Invariant 1 and Invariant 2 and has (log 3 ) worst-case depth and ( log 2 + ) space.
Proof. All edge updates can be partitioned into B and B in parallel in (1) depth. Then, it remains to bound the depth of Algorithm 2 and Algorithm 3.
Algorithm 2 iterates through all = log 2 levels sequentially. By Lemma 3.9, no vertices on level ≤ will violate Invariant 1 after processing level . Thus, by the end of the procedure no vertices violate Invariant 1. By Lemma 3.7, Invariant 2 was never violated during Algorithm 2. Thus, both invariants are maintained at the end of the algorithm. Since we iterate through (log 2 ) levels and, in each level, we require checking the neighbors at one additional level which can be done in parallel in (1) depth, the total depth of this procedure is (log 2 ). To resize the dynamic array, we require (log ) depth whenever the array becomes too large or too small to compute the offsets by which to insert the new elements. For each level, an additional depth of (log ) might be necessary to compute the element offsets and then resize the arrays in (1) depth. Then, Algorithm 2 requires (log 3 ) worst-case depth.
Algorithm 3 iterates through all = log 2 levels sequentially. By Lemma 3.8 and Lemma 3.10, after processing level , no vertices in a level higher than + 1 will have dl( ) ≤ + 1 and no vertices on levels ≤ will violate Invariant 1. Thus, by the end of the procedure all vertices satisfy Invariant 2. Furthermore, Invariant 1 was never violated due to Lemma 3.8. There are (log 2 ) levels and for each level we require running Algorithm 4 to obtain the dl( ) of each affected vertex that should be moved to each level.
Running Algorithm 4 requires (log log ) depth to obtain the first level that satisfies invariants for each affected vertex and (log log ) depth for the final binary search that determines the closest level to ℓ ( ) that satisfies the invariants. In conclusion, Algorithm 3 requires (log 3 ) worst-case depth.
In general, Algorithm 1 requires (log 3 ) worst-case depth. □ Corollary 3.12. Algorithm 1 returns a randomized level data structure that maintains Invariant 1 and Invariant 2 and has (log 2 log log ) depth, whp, and ( log 2 + ) space.
Proof. The proof is the same as the proof of Lemma 3.11 except we replace dynamic arrays with parallel hash tables. Simultaneously changing the values within the hash table require (log * ) depth whp. Then, the depth per level of the structure is dominated by Algorithm 4. Thus, the total depth of our randomized algorithm is (log 2 log log ) whp, and ( log 2 + ) space. □ The additional log 2 space comes from needing to store the dynamic arrays for each vertex in the graph. We show that with slightly more complicated data structures involving linked lists, we can obtain space-efficient structures.
Corollary 3.13. Algorithm 1 returns a space-efficient, deterministic, level data structure that maintains Invariant 1 and Invariant 2 and has (log 4 ) worst-case depth.
Proof. The proof is the same as the proof of Lemma 3.11 except we replace Algorithm 4 with an (log 2 ) linear in number of levels search. The specific data structure we use for each vertex is a linked list with each node of the linked list representing a level ≤ ℓ ( ) − 1 which contains one or more neighbors of . Then, each node in the linked list contains a pointer to a dynamic array containing the neighbors in that level. The linked list has size at most (log 2 ). Thus, the total depth is (log 4 ). □ Our work bound uses potential functions similar to those presented in Section 4 of [8]. We show our parallel algorithm serializes to a set of sequential steps that can be analyzed using these potential functions. Because the potential functions are very similar to those in [8], we leave the discussion to Appendix B. Together, we obtain the work and depth bounds shown in Theorem 1.2.

(2 + )-Approximation of Coreness
The coreness estimate,ˆ( ), is an estimate of the coreness of a vertex . As mentioned previously in Section 3.5, we compute an estimate of the coreness using information about the level of the vertex . Here, we show that such an estimate provides us with a (2 + )approximation to the actual coreness of for any constant > 0. (We can find an approximation for any fixed by appropriately setting our parameters and .) To calculateˆ( ), we first find the largest index of a group , where ℓ ( ) is at least as high as the highest level in . We prove that our PLDS maintains a (2 + 3/ ) (1 + ) approximation of the coreness value of each vertex, for any constants > 0 and > 0, if we useˆ( ) as computed in Definition 3.14. Therefore, we obtain the following lemma giving the desired (2+ )approximation, a 2-factor improvement on the previous approximation bounds. Previous works were only able to obtain a (4 + )approximation theoretical bound [69]. We see in our experimental analysis that such a bound improves the maximum error of our algorithm compared to previous algorithms that obtain similar average errors. Given fixed and , the maximal error of our algorithm is given by (2 + 3/ )(1 + ).
We first show some properties ofˆ( ) and then we show that we can obtain an approximate coreness number by looking atˆ( ). To prove this case, we consider the following process, which we call the pruning process. Pruning is done on a subgraph ⊆ . We use the notation ( ) to denote the degree of in the subgraph induced by . For a given subgraph , we prune by repeatedly removing all vertices in whose ( ) < (1+ ) ′ (2+3/ ) (1+ ) . Note that in this argument, we need only consider levels from the same group ′ before we reach a contradiction, so we assume that all levels are in the group ′ . Let represent the number of levels below level ( ′ ). (Recall that becauseˆ( ) ≥ (1+ ) ′ , ℓ ( ) ≥ ( ′ ). If we consider a level ℓ ( ) > ( ′ ), then the up*-degree cannot decrease due to Invariant 2 becoming stricter. This only makes our proof easier, and so for simplicity, we consider ℓ ( ) = ( ′ ).) We prove via induction that the number of vertices pruned from the subgraph induced by ( ′ )− must be at least Thus, we have proven our argument for the ( + 1)-st induction step. Note that for = ⌈log (2+3/ ) (1+ )/2 (2 + 1)⌉, we have ≤ 2⌈log (1+ ) ( )⌉. This is because, since we pick to be a constant, 2 + 3/ > 2 and for large enough , log (2+3/ ) (1+ )/2 (2 + 1) ≤ 2⌈log (1+ ) ( )⌉. Then, by our induction, we must prune at least 2 + 1 vertices at this step, which we cannot because there are at most 2 vertices. This last step holds because all vertices with degree 0 must be on the first level. Hence, all vertices not on level 0 must be adjacent to at least one edge, and ≤ 2 . Thus, our assumption is incorrect and we have proven our desired property. □ Using our deterministic and space-efficient data structures, we can obtain the following additional results.  Using this data structure, we show a bound for the outdegree if we orient all edges towards neighbors at higher levels and orient edges from higher ID to lower ID in the same level.
Corollary 3.19. The PLDS maintained by Algorithm 1 provides a low out-degree orientation of out-degree at most (8 + ) where is the arboricity, if all edges are oriented from vertices in lower levels to vertices in higher levels and edges between vertices in the same level are oriented from higher ID to lower ID.
Proof. Let the degeneracy of the graph be . As is well-known, the degeneracy of the graph is equal to where is the maximum -core of the graph. Furthermore, it is well-known that ≤ 2 . By Lemma 3.16, the vertices in the largest -core in the graph are in a level with group number at most log (1+ ) ((2+3/ ) )+ 1. This means that the up-degree of each vertex in that group is at most (2 + 3/ )(1 + ) log (1+ ) ( (2+3/ ) ) = (4 + ) for any constant > 0 for an appropriate setting of > 0. We then obtain an (8+ ) out-degree orientation where is the arboricity of the graph. □ Our data structure also provides an approximation of the densest subgraph within the input graph by the Nash-Williams theorem.
Corollary 3.20. The PLDS maintained by Algorithm 1 provides an (8 + )-approximation on the density of the densest subgraph within the input graph.

Static (2 + )-Approximate -core
Due to the P-completeness of -core decomposition for ≥ 3 [4], all known static exact -core algorithms do not achieve polylogarithmic depth. We introduce a linear work and polylogarithmic depth (2 + )-approximate -core decomposition algorithm based on the parallel bucketing-based peeling algorithm for static exact -core decomposition of Dhulipala et al. [19]. The algorithm maintains a mapping from ∈ to a set of buckets, with the bucket for a vertex ( ) changing over the course of the algorithm. The algorithm starts at = 0, peels all vertices with degree at most , increments , and repeats until the graph becomes empty. The -core value of is the value of when is peeled. We observe that the dynamic algorithm in this paper can be combined with a peeling algorithm like the above to yield a linear-work approximate -core algorithm with polylogarithmic depth. Algorithm 5 shows pseudocode for our approximate -core algorithm, which computes an approximate coreness value for each vertex. The algorithm sets the initial coreness estimates, [ ], of each vertex to its degree (Line 1). Then, it maintains a parallel bucketing data structure , which maps each vertex to the ⌈log 1+ [ ]⌉'th bucket (Line 2). It initializes a variable finished = 0 to keep track of the number of vertices peeled and a variable = 0 used to compute the approximate core values (Line 3). The rest of the algorithm performs peeling, where the peeling thresholds are powers of (1 + ). The peeling loop (Line 4-Line 15) first extracts the lowest non-empty bucket from (Line 5), which consists of , a set of vertex IDs of vertices that are being peeled, and the bucket number bkt. If more than log 1+ ( ) rounds of peeling have occured at the threshold (1 + ) , the algorithm increments (Line 6). Next, the algorithm computes in parallel an array of pairs ( , ), where is a neighbor of some vertex in and is the number of neighbors of in (Line 8). Finally, the algorithm computes in parallel the new buckets for the affected neighbors (Line 10-Line 14). The coreness estimate is updated to the maximum of the peeling threshold of the previous level and the current induced degree of after of its neighbors are removed. Finally, the algorithm updates the buckets using the new coreness estimates for the updated vertices (Line 15), which can be done in parallel using our bucketing data structure. We provide an example of this algorithm below.
Example 4.1. Fig. 6 shows a run of Algorithm 5 on an example graph. Given the parameters = = 1, the two buckets that the vertices of the input graph (shown in ( )) are partitioned into are bucket index 1 (green vertices) and bucket index 2 (purple vertices). Vertices , , , and have degree 2 so they are put into the bucket with index ⌈log 2 (2)⌉ = 1. Since , , , and have degree ≥ 3, they are put into the bucket with index ⌈log 2 (3)⌉ = 2.
Since the bucket with index 1 has the smaller bucket index, we peel off all the vertices in that bucket (the green vertices) and we assign the core estimate of (1 + ) 1 = 2 to all vertices in that bucket (shown in ( )). We update the buckets of all neighbors of the peeled vertices; however, since , , , and all still have degree ≥ 3, they remain in the bucket with index 2. Finally, we peel bucket index 2 and assign all vertices in that bucket an estimate of (1 + ) 2 = 4 (shown in ( )). In this example, the estimates produced are 3-approximations of the real coreness values.
We prove below that Algorithm 5 finds an (2 + )-approximate -core decomposition in ( ) expected work and (log 3 ) depth whp, using ( ) space, as stated in Theorem 1.1. Our proof uses the quality guarantees in Lemma 8 of [27], as well as an efficient parallel semisort implementation [31].
Proof of Theorem 1.1. Our approximation guarantee is given by Lemma 8 of [27]. Our algorithm uses a number of data structures that we use to obtain our work, depth, and space bounds. Our parallel bucketing data structure (Line 2) can be maintained via a sparse set (hash map), or by using the bucketing data structure from [19]. The outer loop iterates for (log ) times (Line 4). Within each iteration of the outer loop, we iterate for (log (1+ ) ) = (log ) rounds for constant . After obtaining a set of vertices, we update the buckets using semisort in (log ) depth whp [19]. Thus the overall depth of the algorithm is (log 3 ) for any constant > 0. The work of the algorithm can be bounded as follows. We charge the work for moving a vertex from its current bucket to a lower bucket within a given round to one of the edges that was peeled from the vertex in the round. Thus the total number of bucket moves done by the algorithm is ( ). Each round of the algorithm also peels a number of edges and aggregates, for each vertex that has a neighbor in the current bucket, the number of edges incident to this vertex that are peeled (the variable in the algorithm). We implement this step using a randomized semisort [31]. Since 2 edges are peeled in total, the overall work is ( ) in expectation.
Lastly, we bound the space used by the algorithm. There are a total of (log 1+ ) = (log ) buckets for any constant > 0. Each vertex appears in exactly one bucket, and thus the overall space of the bucketing structure is ( ). The algorithm also semisorts the edges peeled from the graph in each step. Since all edges could be peeled and removed within a single step, and thus semisorted the overall space used by the algorithm is ( ). □ The approximation guarantees provided by our algorithm are essentially the best possible, under widely believed conjectures. Specifically, Anderson and Mayr [4] show that the optimization version of the High-Degree Subgraph problem, namely to compute the largest core number, or degeneracy of a graph cannot be done better than a factor of 2. Thus, obtaining a polynomial work and polylogarithmic depth (2 − )-approximation to the coreness value of each vertex would yield a 2 − approximation to the optimization version of the High-Degree Subgraph problem, and show that P = NC, contradicting a widely-believed conjecture in parallel complexity theory.
In recent years, several results have given parallel algorithms that obtain a (1 + )-approximation to the coreness values in distributed models of computation such as the Massively Parallel Computation model [25,27]. These results work by performing a random sparsification of the graph into a subgraph that approximately preserves the coreness values. They then send this subgraph to a single machine, which runs the sequential peeling algorithm on the subgraph to find approximate coreness values. Crucially, this second peeling step on a single machine can have Θ( ) depth, and thus, this approach does not yield a polylogarithmic depth algorithm in the work-depth model of computation.

Experimental Evaluation
Setup. We use c2-standard-60 Google Cloud instances, which have 30 cores with two-way hyper-threading (3.1 GHz Intel Xeon Cascade Lake) and 236 GiB memory, and m1-megamem-96 Google Cloud instances, which have 48 cores with two-way hyperthreading (2.0 GHz Intel Xeon Skylake) and 1433.6 GB memory. Our programs use a work-stealing scheduler, and are compiled using g++ (version 7.5.0) with the -O3 flag. We terminate experiments that take over 3 hours. We test our algorithms on real-world undirected graphs from SNAP [44], the DIMACS Shortest Paths challenge road networks [18], and Network Repository [58], shown in Table 2, namely dblp, brain, wiki, orkut, friendster, stackoverflow, usa, ctr, youtube, and livejournal. We also used twitter, a symmetrized version of the Twitter network [42]. We remove duplicate edges as well as zero degree edges and self-loops. The table reflects the size of each graph after this preprocessing. Both stackoverflow and wiki are temporal networks obtained from the SNAP database. For these two networks, we maintain the same order of edge insertions and deletions in the order that they occur temporally as provided by SNAP. usa and ctr are two high diameter road network graphs and brain is a highly dense network of the human brain where the largest -core has size ≥ 1200.
All experiments are run on the c2-standard-60 instances, except for twitter and friendster, which are run on the m1-megamem-96 instances as they require more memory. The edge updates for the dynamic algorithms (for all except the temporal networks) are generated by taking a random permutation of a list containing two copies of each edge, where the first appearance of an edge is an insertion, and the second appearance is a deletion. Batches are generated by taking regular intervals of the list. For the experiments on insertion-only batches, we ignore the second appearance of each edge and, likewise, the first for deletion-only batches.
For the static algorithms in the batch-dynamic setting, within each batch we order all insertions in the batch before all deletions. Then, we generate two static graphs per batch, one following all insertions, and the other following all deletions. We re-run the static algorithms on each static graph generated in this manner, to obtain comparable per-batch running times. 5 Algorithms. Unless otherwise noted, we run our parallel algorithms using all available cores with two-way hyper-threading. We make one modification in our parallel implementation of our insertion procedure from our theoretical algorithm which is instead of moving vertices up level-by-level, we perform a parallel filter and sort that calculates the desire-level of vertices we move up. This results in more work theoretically, but we find that, practically, it results in faster runtimes. Also, notably, in practice, we optimized the performance of our PLDS by considering ⌈log (1+ ) ⌉/50 levels per group instead of ⌈log (1+ ) ⌉. We also implemented a version of our structure that exactly follows our theoretical algorithm and compared the performance of both structures. We see that even such a simple optimization resulted in massive gains in performance.
We test the following implementations: LDS: the sequential dynamic approximation algorithm using the level data structures of Bhattacharya et al. and Henzinger et al. [8,33]; PLDS: our parallel batch-dynamic approximation algorithm; PLDSOpt: our optimized parallel batch-dynamic approximation algorithm (that uses less levels per group); ApproxKCore: our parallel static approximation algorithm; ExactKCore: the parallel static exact algorithm of Dhulipala et al. [19]; Hua: the parallel, batch-dynamic exact algorithm of Hua et al. [34]; and Sun: the sequential dynamic approximation algorithm of Sun et al. [69].
We implemented our algorithms using the Graph Based Benchmark Suite [20], and we use the atomic compare-and-swap and fetch-and-add instructions. We also used a concurrent hash table with linear probing [66]

for the level sets [ ] [ ] and [ ].
For deletions, we used the folklore tombstone method: when an element is deleted, we mark the slot in the table as a tombstone, which can be reused, or cleared during a table resize. Accuracy vs. Running Time. We evaluated the empirical error ratio of the per-vertex core estimates given by our algorithms (LDS, PLDS, and PLDSOpt) and Sun on dblp and livejournal, using batches of size 10 5 and 10 6 , respectively, consisting of both insertions and deletions. The results are shown in Fig. 7. The figure shows the  [69]). We also tested sun = 1.1, as done in Sun et al.'s code [69]. In this setting, the theoretical bounds given by Sun et al. [69] no longer hold, but it gives better estimates empirically. We compare this heuristic setting to a similar heuristic in our PLDS and LDS algorithms, where we pick a value of < 3 such that (2 + 3/ ) = 1.1 for = {0.4, 0.8, 1.6, 3.2}. Overall, we see that using theoretically efficient parameters, our PLDSOpt, PLDS and LDS algorithms are faster than Sun, for parameters that give similar average and maximum per-vertex core estimate error ratios. For dblp, PLDSOpt achieves 22. .82x and PLDS achieves 11.15-25.02x speedups over Sun, and for livejournal, PLDSOpt achieves 27.64-497.63x and PLDS achieves 36.44-57.43x speedups over Sun. Using the same parameters, for dblp, PLDSOpt achieves a 3.43-57.124x speedups over PLDS; for livejournal, the speedups are 1.70-51.36x. Moreover, PLDS achieves 1.41-5.23x speedups over LDS on dblp, and 3.30-9.57x speedups over LDS on livejournal, using the same parameters; PLDS does not show as much speedup over LDS on dblp because it is a small graph. PLDS also has much lower maximum error ratios compared to Sun and PLDSOpt on parameters that give similar average error ratios. PLDSOpt gives similar maximum errors to Sun with maximum error factors of 4-58 compared to Sun's maximum error factors of 1.5-47 for dblp; for livejournal, PLDSOpt gives maximum error factors of 3-136.3 compared to Sun's maximum error of 4-182. The heuristic settings in both our algorithms and Sun give better approximations at the cost of speed. We achieve similar error ratios with up to 3.96x speedup using PLDS on dblp, and up to 22.64x speedup using PLDS on livejournal. Also, PLDS achieves 4.28-11.01x speedup over LDS on dblp, and 8.71-11.43x speedup over LDS on livejournal. Unfortunately, PLDSOpt was not able to achieve comparable error ratios for these settings.
For the rest of the experiments, we fix = 0.4 and = 3; these parameters offer a reasonable tradeoff between approximation error and speed, as shown in Fig. 7. We also focus on insertion-only and deletion-only batches since inputs are initially filtered anyways into such batches. Comparison with Hua et al. We also compare with a parallel batch-dynamic algorithm for exact -core by Hua et al. [34]. We obtained a multicore implementation of their code and tested their code under the same experimental conditions as our code. Although the experiments in [34] tested the runtime of randomly sampling a batch of insertions or deletions, we also tested our code under such settings and found that it obtained similar speedups to the experiments run under our setting; thus, we present here the results under our experimental setting. Hua et al. included a timing function in their code which we use to time their code. However, this timing function does not include the time to process the graph and maintain their data structures; we include all such times (for updating the graph and maintaining our data structures) in our code. If we include this time in Hua et al's implementation, their running times increase by up to 8x for some experiments. But for our experiments, we use the original timing functionality in Hua et al. 's code without this additional time.

Experiments on Insertions
Batch Size vs. Running Time. Fig. 8 (first row) shows the average insertion-only per-batch running times on varying batch sizes for LDS, PLDS, PLDSOpt, ExactKCore, and ApproxKCore on dblp and livejournal. ExactKCore and ApproxKCore recompute the -core decomposition on the current batch as well as all previously inserted edges. We see that PLDSOpt is 16.55-6205.19x and PLDS is 1.76-51.81x faster than LDS, and ApproxKCore is 1.37-1.67x faster than ExactKCore overall. PLDSOpt is also 8.47-18.91x faster than PLDS. Moreover, for livejournal, ExactKCore and ApproxKCore both time out for small batch sizes. For dblp, we see that PLDSOpt is up to 75.94x faster, PLDS is up to 7x faster than ApproxKCore for small batch sizes, and even our sequential LDS is up to 3.98x faster than ApproxKCore. Against Hua, PLDSOpt achieves a speedup over all batches from 5.17-16.43x for dblp and 15.97-114.52x for livejournal. PLDS achieves speedups over Hua for the smaller batches, a speedup of 1.51x for dblp and up to 13.51x speedup for livejournal. Finally, ApproxKCore achieves speedups of up to 33.90x for dblp and 42.02x for livejournal over Hua for the larger batch sizes. Thread Count vs. Running Time. We focus on the parallel speedups of our dynamic algorithms since the parallel speedups of static algorithms have been well-studied. Fig. 9 (top row) shows the scalability of PLDSOpt, PLDS, and Hua with respect to their singlethread running times on dblp and livejournal for insertion-only batches. We display the scalability of the algorithms on dynamic inputs, of insertion-only batches of size 10 6 . PLDSOpt and PLDS achieve up to 30.28x and 26.46x self-relative speedup, respectively. Hua achieves up to a 2.07x self-relative speedup. We see that our PLDS algorithms achieve greater self-relative speedups than Hua. Additional Graphs. Fig. 10 (top) shows the runtimes of PLDSOpt, Hua, PLDS, ExactKCore, and ApproxKCore on additional graphs, using insertion-only batches, all of size 10 6 . Hua, ExactKCore and ApproxKCore timed out on twitter and friendster. For the remaining graphs, ApproxKCore is up to 1.85x faster than ExactKCore on average per batch. For the smaller graphs (dblp, youtube, and orkut), ApproxKCore is up to 4.55x faster than PLDSOpt and up to 48.29x faster than PLDS on average per batch, because 10 6 is a relatively large batch size for these graphs, so it is faster to re-run our static algorithm compared to our batch-dynamic algorithm. For the larger graphs (except for the graphs where ApproxKCore times out), PLDSOpt achieves up to a 13.09x speedup and PLDS achieves up to a 7.41x speedup against ApproxKCore. We see that among these graphs both PLDSOpt and PLDS perform particularly well in the high-diameter road networks suggesting that the dynamic algorithms perform many less changes to the data structures than the static algorithm for high-diameter (sparser) networks. For the largest graphs (twitter and friendster), PLDSOpt and PLDS are orders of magnitude faster as ApproxKCore times out.
Compared against Hua, PLDSOpt achieves speedups of 6.20-58.66x on all graphs that Hua did not time out for and is orders of magnitude faster on twitter and friendster since Hua times out. Except for the two smallest graphs, dblp and wiki, PLDS achieves speedups of 1.30-49.02x for all graphs that Hua did not time out for and is orders of magnitude faster on the two largest graphs. On brain, twitter, and friendster, PLDSOpt achieves 13.83x, 5.82x, and 12.40x speedups, respectively, over PLDS, suggesting the optimization is most beneficial for dense graphs.
We also compared the performance of ApproxKCore and Exac-tKCore using the full graph on all datasets. We found ApproxKCore to be 1.7-3.9x faster than ExactKCore, with an average coreness error ratio of 1.044-1.172. Accuracy of Approximation Algorithms. We also computed the average and maximum errors of all of our approximation algorithms for our experiments shown in Fig. 10. The data for these error ratios are shown in Table 3. We tested the errors for = 0.4 and = 3. According to our theoretical proofs, the maximum error (for PLDS) should be (2+3/3) · (1+0.4) = 4.2. We see that indeed the maximum empirical error for PLDS falls under this hard constraint. PLDSOpt achieves an average error of 1.359-2.118 on insertion batches (left half) of Table 3 compared to errors of 1.593-3.363x for PLDS and 1.010-4.175 for ApproxKCore. For max error, PLD-SOpt achieves a max error of 3 (less than the theoretical optimal) compared to 3-4.193 for PLDS and 3-4.305 for ApproxKCore. For twitter and friendster, we sampled error counts uniformly at random with probability 1/10 due to our timeout constraints. PLDS and ApproxKCore computations timed out on both of these datasets (even with sampling). We see that decreasing the number of levels improves the error ratio for insertion-only batches. Space Usage. Finally, we tested the space usage of our parallel batch-dynamic programs against the space usage needed by Hua. We implemented functions that counted the space usage of the entire level data structure used in our programs and the data structures used in the Hua code using the sizeof operator. Fig. 11 (top row) shows the results of our experiment. As expected, since our data structures require ( log 2 + ) asymptotic space, our space usage for PLDS is up to 63.87x more and 62.50x more than Hua for dblp and livejournal, respectively. However, our PLDSOpt uses less memory than Hua in most settings (up to 1.53x factor less memory) for dblp and up to 1.08x additional space in a few cases; for livejournal, it uses up to 1.72x additional space.

Experiments on Deletions
In this subsection, we present deletion-only experimental results of our LDS, PLDSOpt, PLDS, and ApproxKCore algorithms using the same environment as our insertion-only experiments. In general, for our batch-dynamic implementations, deletions are faster than insertions due to the fact that we move each vertex at most once. Specifically, when determining vertices to move up a level,    in order to check the requisite invariants, each vertex must maintain its neighbors in the levels below, keyed by level number. This takes more work than the symmetric computation for deletions, where each vertex simply maintains the set of neighbors in the levels above and needs not key these neighbors by their level numbers. Furthermore, PLDSOpt results in slightly greater error for the deletion case because we decrease the number of levels.
Batch Size vs. Running Time. Fig. 8 (bottom row) shows the average deletion-only per-batch running times on varying batch sizes for LDS, PLDSOpt, PLDS, ExactKCore, and ApproxKCore on dblp and livejournal. ExactKCore and ApproxKCore recompute the -core decomposition on the graph after removing the current batch, as well as all edges in previous batches. We see that PLDSOpt is up to 7.17x faster than PLDS, PLDS is up to 24.75x faster than LDS, and ApproxKCore is up to 1.59x faster than ExactKCore overall. Compared to using insertion-only batches, PLDS is slower than LDS on smaller batches, and the speedup of PLDS over LDS is also smaller. We believe that this is due to the lower amount of work in the desire level computations for deletion-only batches, where LDS is faster at processing deletion-only batches compared to insertiononly batches. However, the speedups of PLDSOpt and PLDS over Hua are 3.39-44.58x and 1.2-7.89x, respectively, for dblp and 1.71-45.01x and 1.27-6.59x, respectively, for livejournal. The additional speedups of PLDS over Hua is due to our more efficient deletion procedure that does less work than our insertion procedure. Moreover, for livejournal, ExactKCore and ApproxKCore both time out for the small batch sizes. For dblp, we see that PLDS is up to 26.61x faster than ApproxKCore for small batch sizes, and even our sequential LDS is up to 50.38x faster than ApproxKCore. For ApproxKCore and ExactKCore, the running times are similar to the insertion-only case, except for large batch sizes on dblp, where the deletion-only batches are faster to process. This is because dblp is small, with fewer than 3 × 10 6 edges, and so in the deletion-only setting, we are left with a relatively small graph (or an empty graph in the 10 7 batch size case) after the first batch. On the other hand, in the insertion-only setting, we have almost half of the graph (or the full graph in the 10 7 batch size case) after the first batch. Thus, there is greater processing required overall in the insertion-only setting, for small graphs with large batch sizes. Thread Count vs. Running Time. Fig. 9 (bottom row) shows the scalability of PLDS with respect to its single-thread running times on dblp and livejournal for deletion-only batches of size 10 6 . PLDSOpt achieves up to a 32.02x self-relative speedup and PLDS achieves up to 25.33x self-relative speedup, similar to the speedups obtained in the insertion-only setting. Unlike the case with insertions, Hua achieves no speedup on dblp and up to a 1.30x selfrelative speedup on livejournal. Additional Graphs. Fig. 10 (bottom graph) shows the runtimes of PLDSOpt, Hua, PLDS, ExactKCore, and ApproxKCore on the remaining graphs, using deletion-only batches of size 10 6 . Hua, ExactKCore and ApproxKCore timed out at 3 hours on twitter and friendster. PLDSOpt is uniformly faster than all other programs for all graphs except dblp, achieving a maximum speedup of 23.45x against PLDS, 19.64x against ApproxKCore, and 52.36x against Hua (on all graphs that did not time out). These results are similar to those obtained for insertions, although the slight speedup could be due to fewer levels causing deletions to achieve greater speedup than insertions. For youtube and orkut, ApproxKCore is up to 1.4x faster than ExactKCore on average per batch. Additionally, for these graphs, ApproxKCore is up to 2.26x faster than PLDS on average per batch, for the same reason as discussed earlier (10 6 is a relatively large batch size for these graphs, and so it is faster to re-run our static algorithm compared to our batch-dynamic algorithm). For the larger graphs (twitter and friendster), PLDS is orders of magnitude faster, as ApproxKCore times out. Accuracy and Space Usage. Table 3 shows a slight increase in the maximum error for PLDSOpt, with a max error of 6. This is expected theoretically; recall the theoretical upper bound on the error is 4.2 (followed by PLDS). PLDS and ApproxKCore do not show noticeable differences in error. Fig. 11 (bottom row) shows the space usage of PLDS, PLDSOpt, and Hua for deletions. Similar to insertions, PLDSOpt uses less space than Hua for most cases for dblp, up to 1.57x factor less space. PLDSOpt has a maximum space usage of 1.07x and 1.69x for dblp and livejournal over Hua, and PLDS a 48.50x and 21.15x factor over Hua.

Conclusion
We presented a work-efficient parallel batch-dynamic level data structure that gives a (2 + )-approximate -core decomposition. Our approach also gave a static approximate -core algorithm that is to the best of our knowledge the first work-efficient algorithm with polylogarithmic depth for this problem. We studied sharedmemory implementations of all of our algorithms and confirmed the practical applicability of our approach.

A Additional Data Structure Implementations
In addition to the randomized data structures presented in Section 3.4 of our main paper, we present two additional sets of data structures that we can use to obtain a deterministic and a space-efficient (2 + )-approximate -core algorithms.
The work of all of our randomized, deterministic, and spaceefficient algorithms are the same; however, using randomization allows us to obtain a better depth with slightly less complicated data structures.

Deterministic Data Structures
We initialize an array , of size . Each vertex is assigned a unique index in . The entry for the 'th vertex, [ ], contains a pointer to a dynamic array that stores the neighbors of vertex at levels ≥ ℓ ( ). Each vertex also stores another dynamic array, , that contains pointers to a set of dynamic arrays storing the neighbors of partitioned by their levels where < ℓ ( ). Specifically, we maintain a separate dynamic array for each level from level 0 to level ℓ ( ) − 1 storing the neighbors of at each respective level. We also maintain the current level of each vertex in an array.
To perform a batch of insertions into a dynamic array, we insert the elements at the end of the array. The array is resized and doubles in size if too many elements are inserted into the array (and it exceeds its current size). For a batch of deletions, the deletions are initially marked with a "deleted" marker indicating that the element in the slot has been deleted. A counter is used to maintain how many slots contain "deleted." Then, once a constant fraction of elements (e.g. 1/2) has "deleted" marked in their slots, the array is cleaned up by reassigning vertices to new slots and resizing the array.
( + ) Total Space Data Structures Here we describe how to reduce the total space usage of our data structures to ( ). All of our previous data structures use ( log 2 + ) space, which means that when = ( ), we use space that is superlinear in the size of the graph. To reduce the total space to ( ), we maintain two structures for . We can use either the deterministic or randomized structures for the other structures. Each is maintained as a linked list. The 'th node in the linked list maintains the number of neighbors of at the 'th non-empty level (a non-empty level is one where has neighbors at that level) that is less than ℓ ( ). The node representing a level is removed from the linked list when the level becomes empty. Each node in contains pointers to vertices at the level represented by the node. Each vertex then contains pointers to every edge it is adjacent to and every edge contains pointers to the two nodes in the two linked lists representing the levels in which endpoints of the edge reside. Using either dynamic arrays or hash tables for the lists of neighbors allow us to maintain these data structures in ( ) space. Since we only maintain a node in our linked list for every non-empty level, our linked list contains precisely the number of elements equal to 2 .

B Potential Argument for Work Bound
Our work bound uses the potential functions presented in Section 4 of [8]. We show that we can analyze our algorithm using these potential functions and our parallel algorithm serializes to a set of sequential steps that obey the potential function. We obtain the following lemma by the potential argument provided in this section.

B.1 Proof of Work Bound
Unlike the algorithm presented in [8,33], in each round, to handle deletions, we recompute the dl( ) of any vertex that we want to move to a lower level. Specifically, we compute and move to the closest level that satisfies both Invariant 1 and Invariant 2. This is a different algorithm from the algorithm presented in [8,33], and so we present for completeness a work argument for our modified algorithm. The work bound we present accounts for the work of any one movement up or down levels using the potential function argument of [8]. Note that this potential function also gives us the amortized work per edge update since there exists a corresponding set of sequential updates that cannot do less work than the set of parallel updates.
Charging the Cost of Moving Levels The strategy behind our potential function is use the increase in our potential function due to edge updates to pay for the decrease in potential due to vertices moving up or down levels. We can then charge our costs to the increase in potential due to edge updates. Below, we bound the increase in potential due to edge updates and the decrease in potential due to vertex movements.
We use the following potential function to calculate our potential. First, recall some notation. Let be the set of vertices in levels to − 1. In other words, = Using the potential functions defined in [8], for some constant > 0: We first calculate the potential changes for insertions and deletions of edges. Insertion The insertion of an edge ( , ) creates a new edge with potential Ψ( , ). The new potential has value at most 2 + 1. With an edge insertion Φ( ) and Φ( ) cannot increase. Thus, the potential increases by at most 2 + 1.
Deletion The deletion of edge ( , ) increases potentials Φ( ) and Φ( ) by at most 2 . It does not increase any other potential since the potential of edge ( , ) is eliminated.
First it is easy to see that the potential Π is always nonnegative. Thus, we can use the positive gain in potential over edge insertions and deletions to pay for the decrease in potential caused by moving vertices to different levels. Now we discuss the change in potential given a movement of a vertex to a higher or lower level. Moving such a vertex decreases the potential and we show that this decrease in potential is enough to pay for the cost of moving the vertex to a higher or lower level.
A vertex moves from level to level dl( ) < due to Algorithm 3 Since vertex moved down at least one level, this means that prior to the move, its up*-degree is up * ( ) < (1 + ) (ℓ ( )−1) . It is moved to a level dl( ) where its up*-degree is at least (1 + ) (dl( )−1) and its up-degree is at most (2 + 3/ ) (1 + ) (dl( )) (or it is moved to level 0).
The potential before the move is at least since we only move a vertex to a lower level if up * ( ) < (1 + ) (ℓ ( )−1) and we move it to the closest level dl( ) where Invariant 2 is no longer violated. To derive the second term, since we moved vertex to level dl( ), we know that its degree | ( , dl( ) )| < (1 + ) (dl( )) (otherwise, we could've moved to level dl( ) + 1). Then, substituting (1 + ) ( ) for all levels ≥ dl( ) into Φ( ) allows us to obtain ℓ ( )−1 =dl( ) ( + 3)(1 + ) ( ) . Then, when it reaches its final level, we know that it is at the highest level it can move to or at level 0. In both cases, We need to account for two potential increases: the increase in Ψ and the increase in Φ from neighbors of . We first consider the increase in Ψ. The potential increase in Ψ( , ) for every edge ( , ) where ℓ ( ) ≥ dl( ) is at most 2(ℓ ( ) − dl( ))(1 + ) (dl( )) , since has up-degree at most (1 + ) (dl( )) at level dl( ) (otherwise, we can increase its dl( )) and each of these edge's potential gain is upper bounded by 2 for every level in [dl( ), ℓ ( ) − 1].
Furthermore, we need to account for the increase in potential of every neighbor whose edge is flipped by the move. The total increase in Φ is at most (ℓ ( )−dl( ))(1+ ) (dl( )) for every neighbor on levels > dl( ) + 1, since we move to the highest level that satisfies the invariants and ( , dl( )) < (1 + ) (dl( )) . Decreasing the degree of each neighbor by one for each of ( , dl( )) < (1 + ) (dl( )) results in the total increase in Φ.
Then, in total, the potential decrease is at least which is enough to pay for the at most (1 + ) (dl( )) edge flips as well as the (ℓ ( ) − dl( )) work for computing the desire-level. The total number of edge flips is upper bounded by ( , dl( )). Since we moved to dl( ) and not dl( ) + 1, we know that satisfies Invariant 2 at dl( ) and not at dl( ) + 1. Then, this means that | ( , dl( )))| < (1 + ) (dl( )) . Hence, our number of edge flips is also bounded by (1 + ) (dl( )) .
Let be the set of neighbors that has to iterate through within its data structures if goes up a level. The potential decrease for every neighbor of on = ℓ ( ) is 1. The potential decrease for every neighbor on level + 1 is 1. Finally, the potential decrease for every neighbor in levels > dl( ) is 2. Then, the potential decrease for every neighbor in is at least 1 and is enough to pay for the (| |) cost of iterating and moving the neighbors of in its data structures.
Parallel Amortized Work The last part of the proof that needs to be shown is that any set of parallel level data structure operations that is undertaken by Algorithm 2 or Algorithm 3 has a sequential set of operations of the form detailed above (i.e., moving to dl( ) or moving from level to + 1) that consists of the same or strictly larger set of operations.
Lemma B.2. For any set of operations performed in parallel by Algorithm 2 or Algorithm 3, there exists an identical set of sequential operations to the set of parallel operations.
Proof. In Algorithm 2, the parallel set of operations consists of moving all vertices that violate Invariant 1 in the same level up to level + 1. Again, suppose we choose an arbitrary order to move the vertices in level to level + 1. Given two neighbors in the order and , if moves to level + 1, the up-degree of still includes ; since the up-degree of any vertex is not affected by the previous vertices that moved to level + 1, moves to + 1 on its turn. This order provides a sequential set of operations that is equivalent to the parallel set of operations.
In Algorithm 3, the parallel set of operations consists of moving a set of vertices down from arbitrary levels to the same level . We show that there exists an identical set of sequential operations to the parallel operations. First, any vertex whose dl( ) = considered all vertices in levels ≥ − 1 in its calculation of dl( ). Thus, any other vertex moving from a level > to level is included in calculating the desire-level of vertex . Suppose we pick an arbitrary order to move the vertices that have dl( ) = to level . Then, the desire-level of any vertex whose dl( ) = does not change after is moved to level . Hence, when it is 's turn in the order, moves to level . This arbitrary order is a sequential set of operations that is identical to the parallel set of operations. □ Lemma B.3. For a batch of B < updates, Algorithm 1 requires (B log 2 ) amortized work with high probability. The required space is ( log 2 + ) using the randomized data structures.
Proof. Our potential argument handles the cost of moving neighbors of a vertex between different levels. Namely, our potential argument shows that such costs of updating neighbor lists of nodes require (log 2 ) amortized work per edge update to the structure.
Then, it remains to calculate the amount of work of Algorithm 4. We can obtain the size of each neighbor list in (1) work and depth. If we show that the work of running Algorithm 4 is asymptotically bounded by to the work of calculating the set of neighbor vertices that need to be moved between neighbor lists for a vertex, then we can also charge this work to the potential. To compute the first lower bound on dl( ), we maintain a cumulative sum of the total number of neighbors for each vertex at or below the current level ℓ ( ). Then, we sequentially double the number of elements we use to compute the next level. We use ((ℓ − dl( ))) work to compute dl( ).
Finally, we also bound the work of the final binary search. Let be the size of the range of values in which we perform our binary search. The size of the number of possible levels becomes smaller as we decrease our range of values to search. Whenever we go right in the binary search, we perform /2 work. Whenever we go left in the binary search, we also perform at most /2 work. Thus, the total amount of work we perform while doing the binary search is ( ). And by the argument above, the amount of work is | dl( ) \ ℓ ( ) | .
The total work of Algorithm 4 is (| dl( ) \ ℓ ( ) | + (ℓ − dl( ))) which we can successfully charge to the potential. We conclude that the amount of work per update is (log 2 ). □

B.2 Overall Work and Depth Bounds
Our deterministic and space-efficient structures also give the following corollary using our above work-bound arguments.
Corollary B.4. There exists a set of data structures where Algorithm 1 requires (log 2 ) amortized work per update, deterministically, using ( + ) space.
Using Corollary 3.12 and Lemma B.3, we obtain Lemma B.1. Similarly, combining Lemma 3.11 and Corollary B.4 and Corollary 3.13 and Corollary B.4, we obtain the following two corollaries.
Corollary B.5. For a batch of B < updates, Algorithm 1 returns a PLDS that maintains Invariant 1 and Invariant 2 in (B log 2 ) amortized work and (log 3 ) worst-case depth, using ( log 2 + ) space.
Corollary B.6. For a batch of B < updates, Algorithm 1 returns a PLDS that maintains Invariant 1 and Invariant 2 in (B log 2 ) amortized work and (log 4 ) worst-case depth, using ( + ) space.

C Handling Vertex Insertions and Deletions
We can handle vertex insertions and deletions by inserting vertices that have zero degree and considering deletions of vertices to be a batch of edge deletions of all edges adjacent to the deleted vertex. When we insert a vertex with zero degree, it automatically gets added to level 0 and remains in level 0 until edges incident to the vertex are inserted. For a vertex deletion, we add all edges incident to the deleted vertex to a batch of edge deletions. Note, first, that all vertices which have 0 degree will remain in level 0. Thus, there are at most ( ) vertices which have non-zero degree. Because we have (log 2 ) levels in our data structure, we rebuild the data structure once we have made /2 edge updates (including edge updates from edges incident to deleted vertices). Rebuilding the data structure requires ( log 2 ) total work which we can amortize to the /2 edge updates to obtain (log 2 ) amortized work whp. Running Algorithm 2 and Algorithm 3 on the entire set of ( ) edges requires (poly log ) depth whp depending on the specific set of data structures we use.
Lastly, in order to obtain a set of vertices which are re-numbered consecutively (in order to maintain our space bounds), we perform parallel integer sort or hashing.