Parallel Batch-Dynamic Maximal Independent Set Guy Blelloch∗ [email protected]
Andrew Brady∗ [email protected]
arXiv:2604.07515v1 [cs.DS] 8 Apr 2026
Jeremy Fineman‡ [email protected]
Laxman Dhulipala† [email protected]
Jared Lo§ [email protected]
Abstract We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph is updated with batches of edge insertions/deletions, and for each batch a parallel algorithm updates the maximal independent set to agree with the new graph. A batch-dynamic algorithm is considered efficient if it is work efficient (i.e., does no more asymptotic work than applying the updates sequentially) and has polylogarithmic depth (parallel time). In the sequential setting, the best known dynamic algorithms for MIS, by Chechik and Zhang (CZ) [FOCS19] and Behnezhad et al. (BDHSS) [FOCS19], take O(log4 n) time per update in expectation. For a batch of b updates, our algorithm has O(b log3 n) expected work and polylogarithmic depth with high probability (whp). It therefore outperforms the best algorithm even in the sequential dynamic case (b = 1). As with the sequential dynamic MIS algorithms of CZ and BDHSS, our solution maintains a lexicographically first MIS based on a random ordering of the vertices. Their analysis relied on a result of Censor-Hillel, Haramaty and Karnin [PODC16] that bounded the “influence set” for a single update, but surprisingly, the influence of a batch is not simply the union of the influence of each update therein. We therefore develop a new approach to analyze the influence set for a batch of updates. Our construction of the batch influence set is natural and leads to an arguably simpler analysis than prior work. We then instrument this construction to bound the work of our algorithm. To argue our depth is polylogarithmic, we prove that the number of subrounds our algorithm takes is the same as depth bounds on parallel static MIS.
1
Introduction
A maximal independent set (MIS) of an undirected graph is a maximal set of (pairwise) non-adjacent vertices. The MIS is one of the most fundamental graph structures, with many applications and extensive theoretical study [43, 5, 12, 19, 18, 11, 17, 27, 13, 4, 22, 41, 28, 44]. In the sequential static setting,1 one can find an MIS on n vertices and m edges in O(n + m) time in the following way. First, pick any permutation π of the vertices. Then iterate through the vertices in π order, skipping ∗
Carnegie Mellon University, Pittsburgh, PA University of Maryland, College Park, MD ‡ Georgetown University, Washington, DC § University of Hawaii, Honolulu, Hawaii 1 By static, we mean that given a (single) graph, output a response; in contrast, the dynamic setting is one where the graph changes. †
1
the vertices that are eliminated, and otherwise adding the vertex to the MIS and eliminating it and its neighbors from the graph. An MIS generated in this way is called a lexicographic-first MIS (LFMIS). In the parallel static setting Karp and Wigderson [39] described deterministic and randomized polylog-depth parallel algorithms for finding an MIS, but their algorithms require at least Ω(n2 ) work. Luby [43] improved the results with a pair of simple and influential randomized polylog-depth algorithms that require just linear work.2 All of these algorithms are based on finding an independent set, eliminating the neighborhood of this set, and repeating. Generating the LFMIS for a fixed order is known to be NC1 -complete for P [20, 43], and hence unlikely to have a polylogarithmicdepth solution. Blelloch, Fineman, and Shun [17], however, showed that on average, across all orderings, finding the LFMIS is highly parallel; specifically, the longest chain of dependencies, called the dependence depth, is polylogarithmic with high probability (whp)3 , and hence a natural parallelization takes polylog rounds whp. Fischer and Noever [27] then improved the bound to O(log n) depth whp. These results imply another work-efficient polylog-depth randomized algorithm [17]—pick a random π ordering, and then in rounds add a vertex to the MIS as soon as it has no earlier uneliminated neighbor, and eliminate it from the graph as soon as it has an earlier neighbor in the MIS. Henceforth, we will use R-LFMIS to indicate an LFMIS in random order. In the sequential dynamic setting, Assadi, Onak, Schieber, and Solomon [9] present the first non-trivial fully dynamic algorithm supporting updates in O(m3/4 ) time (deterministic, worst case). This was then improved to Õ(n2/3 ) [26, 35], and then to Õ(m1/3 ) time, using randomization and assuming an oblivious adversary [10]. The first sequential dynamic algorithms with polylog time were developed independently by Chechik and Zhang (CZ) [19] and by Behnezhad et al. (BDHSS) [12]. These algorithms are randomized and both run in O(log4 n) time assuming an oblivious adversary.4 They are the current state of the art. Both these algorithms are based on the R-LFMIS and rely on two crucial properties of a R-LFMIS. The first, by Censor-Hillel, Haramaty and Karnin (CHK) [18], is that if an edge or vertex is inserted/deleted, the expected change in the MIS (the recourse) is constant, and in fact at most 1. The second is that when processing the ith vertex in the π order, n the remaining graph has degree O( n log i ) whp [17]. BDHSS also relies on the property that the R-LFMIS dependence graph is shallow whp [17, 27]. A nice property of the CZ and BDHSS algorithms is that they are history independent—no matter the history of updates, the MIS depends only on the current graph and the permutation order, which is chosen at the start. Note that the oblivious adversary assumption is necessary; an adaptive adversary would effectively know the random permutation and could create pathological cases accordingly. In this paper, we present results for MIS in the parallel batch-dynamic setting. In this setting, one maintains a data structure supporting batches of updates that are processed in parallel. One motivation of this setting is the desire to achieve good performance on applications with high update rates, where processing updates sequentially could be too slow. There has been extensive recent 2 As Luby described the algorithms they use O(m log n) work, but they are easily modified to run in O(m) work. Alon, Babai, and Itai [5] independently developed a very similar algorithm a few months later. 3 Formally, we say that f (n, c) = O(g(n)) with high probability if there exists c0 , k such that for c ≥ c0 , there exists n0 such that for n ≥ n0 , f (n, c) ≤ ckg(n) with probability at least 1 − n1c . 4 More precisely, BDHSS achieves a O(log2 n log2 ∆) bound, where ∆ is the maximum degree of a vertex in the graph. Das and Kuszmaul [21] conjectured that by replacing the binary search tree data structure with a van Emde Boas tree, the runtime of BDHSS, at least for lexicographic-first maximal matching, can be improved to O(log3 n log log n).
2
work on graph algorithms in this setting [48, 1, 23, 50, 2, 7, 24, 8, 51, 33, 15, 31, 36, 30, 42, 32, 25]. Such parallel batch-dynamic algorithms have also been used to develop efficient static parallel graph algorithms [6, 29, 52]. We note there has been experimental interest in implementing theoretically efficient batch-dynamic graph algorithms [37, 23, 24]. There has also been work in implementing batch-dynamic MIS specifically, though without theoretical guarantees [49, 45]. Typically, the goal of the batch-dynamic setting is for performance to scale linearly with the number of updates (i.e., if the best sequential dynamic algorithm has f (n) work, the goal would be to achieve roughly bf (n) work on a batch of size b), while also achieving polylog depth. However, some results in this setting are actually able to achieve asymptotically less work per update by removing redundancies [37, 24, 2, 50] in large batches. We know of no prior theoretically-efficient work in the batch-dynamic setting for the maximal independent set problem. Our main result is the following. Theorem (Informal). There exists an algorithm that maintains a maximal independent set under batch insertions and deletions of edges against an oblivious adversary, where for a size-b batch of edge updates, the work is O(b log3 n) in expectation and the depth is O(polylog(n)) whp. We note that even when interpreted as a sequential algorithm, where there is only one update at a time, our result improves the current state of the art [19, 12]. As with CZ and BDHSS, our results are based on R-LFMIS and are history independent. To work in the batch setting, however, we need to develop a new approach to generalize the recourse bounds of CHK. In particular, the CHK bounds rely on the definition of an influence set for a single update—i.e., a set of vertices that could change from being in or out of the MIS due to a single update. They show the size of the influence set to be at most one in expectation. Unfortunately, their definition of influence does not compose across a batch of updates—that is, contrary to intuition, the union of the influence sets for two or more updates made in any order does not necessarily cover the influence set for the updates made together (we show an example in the next section). We therefore develop a significantly different technique and proof for bounding the size of a batch influence set. Towards this end, we define the influence analysis version of a problem. In this influence analysis, some input vertices and edges are initially set to undecided, meaning that their presence in the graph is unknown. As output, one wants to determine the full set of vertices whose MIS status is unknown (or influenced) as a consequence of the unknown inputs. We then show that for the influence analysis version of R-LFMIS: if b input edges and vertices are undecided (can either be in or out of the graph), then the number of influenced outputs (vertices we are not sure are in or out of the MIS) is ≤ b in expectation. This, in turn, implies the same bound on the number of vertices that can change state (in and out of MIS) with a mix of b edge insertions and deletions. The approach we take for this proof is very different than in CHK due to the issue mentioned above. We then develop an algorithm that has some similarities to CZ and BDHSS, but is designed for the parallel setting. In parallel, we process a subset of vertices A whose status has changed (entered or left the MIS) to fix their neighbors as necessary. If we were to choose A to be the unprocessed influenced vertex with minimum permutation time, we would have a sequential algorithm. To process a vertex v at permutation position i, we need to visit its two-hop neighborhood in the graph that remains at step i of R-LFMIS. We perform constant work for each of these visited vertices. We show that the probability that R-LFMIS step i < n/4 contributes a vertex to the n influence set is at most 2bi . Along with the O( n log i ) high probability bound on the degree, this n2 leads almost immediately to a bound of O(log3 n) expected sequential time per update. However, through a careful correctness argument and use of data structures, our algorithm also supports processing many vertices in parallel, even when this involves processing later permutation 3
time vertices before earlier permutation time vertices. This comes with the drawback that we may require processing the same vertex multiple times, thereby increasing the work. Our parallel algorithm mitigates this issue, and achieves work-efficiency with our sequential variant, by processing vertices in a sequence of growing intervals of the permutation (which we call shells), similar to [17]. We also need to bound the number of parallel rounds (or dependence depth) of our algorithm, which does not immediately follow from the bound of the number of rounds of parallel R-LFMIS.
2
Technical Overview
We begin by discussing the challenges with adapting the previous work (CHK [18], CZ [19], BDHSS [12]) to the parallel batch-dynamic setting.5 Challenge: Sequential influence set can iterate many rounds. The influence set (developed by CHK [18]) is a superset of the vertices that actually change mark (actually enter or leave the R-LFMIS). The influence set is defined iteratively. The base set S0 is either empty if the R-LFMIS is valid following the edge update (u, v), or, if the R-LFMIS is no longer valid, S0 contains only the endpoint v that is later in the permutation π. The rth set Sr includes all of Sr−1 , plus the following vertices: the marked vertices that have at least one earlier neighbor in Sr−1 (these vertices may leave the MIS) and the unmarked vertices for which every marked neighbor is in the influence set (these vertices may join the MIS). The influence set grows across iterations in this way until Sr = Sr+1 (until it stabilizes). We refer to the number of rounds of this propagation, i.e., the minimum r for which Sr = Sr+1 as the influence propagation depth. For an example of an influence set, see Figure 1. At first glance, CHK’s influence propagation process seems parallel, with parallel depth proportional to the number of rounds of influence set propagation, especially since the influence propagation depth is shown to be O(1) in expectation. One would therefore hope to leverage known parallel R-LFMIS upper bounds to get high probability bounds on the propagation depth. But even though parallel static R-LFMIS finishes in O(log n) rounds whp, the depth of influence set propagation is not in fact always bounded by the depth of parallel R-LFMIS: there exist graphs and permutations where parallel static LFMIS would take O(log n) rounds, but influence set propagation would take Θ(n) rounds. Figure 2 illustrates such an example, where the influence propagation depth is very high but the dependence depth of LFMIS is low. In particular, consider the simple path of vertices with permutation values 2 to n (for even n), where each vertex i is connected to vertex i + 1. (The figure illustrates n = 12.) Also connect vertex 2 to vertex 4, and vertex 5 to every even vertex with permutation value at least 8. In this graph, vertex 2 and every odd vertex numbered at least 5 are marked (in the MIS). Now consider what happens when the edge (1, 2) is inserted. A static parallel LFMIS would take 3 rounds on the graph without the edge (1, 2), and it would take 4 rounds on the graph that includes that extra edge. But the influence set propagation depth here is n − 3. The reason that the influence set propagation can take much longer than parallel R-LFMIS on certain graphs and permutations is that influence set propagation must wait for all eliminators of a vertex to disappear before adding an initially unmarked vertex to the influence set, whereas dependence depth propagation is based on the earliest eliminator of a vertex. It is still theoretically possible that influence set propagation has a O(polylog(n)) whp bound, but this does not follow 5
A reader interested in understanding our work without relation to prior work can skip to Section 2.1.
4
(2) (0)
(1)
(3) (2)
1
2
3
4
5 6 7 8 9 10 11 12
Figure 1: Example of (sequential) influence set from CHK [18]. The MIS of the graph (before the edge update) is marked in red. Here, the blue edge is the edge being inserted. Vertices circled in blue are influenced. In parenthesis is the round when they join the influence set. We have drawn vertices in π order from left to right (the leftmost vertex is the earliest in the ordering). Figure 2: Example graph where influence round propagation time is greater than dependency depth. The vertices are drawn from π-value left to right (the red vertices thus have permutation values 1,2,5,7,9,11). The red vertices are the marked vertices before the edge update. Consider inserting the dashed edge (1, 2) to the graph. The resulting MIS would be {1, 3, 5, 7, 9, 11}. The influence set would be {2, 3, . . . , 12}. Specifically, S0 = {2},S1 = {2, 3, 4}, S2 = {2, 3, 4, 5},S3 = {2, 3, . . . , 6}, . . . , S9 = {2, 3, . . . , 12}. Thus, influence set propagation takes 9 rounds. Before the edge update, parallel static R-LFMIS would take 3 rounds, and after the edge update, parallel static R-LFMIS would take 4 rounds. By extending the length of the path (as described in main text), the influence set propagation can take n − 3 rounds, whereas the parallel static R-LFMIS would continue to take 4 rounds. from prior work, and we do not attempt to show this. We instead opt to propagate in a different manner designed to inherit the round upper bound from the dependency depth of the graph. Challenge: Constructing a batch influence set. When trying to construct a batch influence set, a natural proposal is to simply change the base case. That is, start with S0 equal to the set of all conflicts immediately caused by the batch insert, but keep the same definitions for Sr for r ≥ 1. Note that for b = 1, this definition is equivalent to CHK’s definition. Surprisingly, however, the batch influence set on a batch B of edge updates can be greater than the union of the influence sets of applying these updates one at a time sequentially to the graph. Thus, CHK’s proof does not bound the size of this batch influence set. For an example of this issue, see Figure 3. Note that the influence set is a superset of the vertices that actually change mark: the influence set can make “mistakes,” which then cause additional vertices to mistakenly join the influence set. When performing updates one at a time, the mistakes from the influence set of one update are erased before the next update begins. However, in a batch update, these mistakes can compound and cause even more vertices to join the influence set. Figure 3 is a small example of such a compounded mistake: the triangles cause the individual mistakes, which combine to influence the starred vertex. Moreover, their proof method critically relies on there being only a single edge update. In their proof, on an edge update (u, v) where u < v, they consider the influence set S ′ that would occur if v were moved to the front of the permutation. Then, they argue that either S = S ′ or S is empty, 1 and that with (informally) |S| probability, S is empty. This all-or-nothing approach fails in the batch setting, because some edges could succeed to cause influence, other edges could fail, and the edges that succeed could combine forces to cause influence neither could cause individually.
5
a
a
a
b
b
Figure 3: Consider the above graph, where vertices that are marked (in the old graph, before the batch update) are red. Consider inserting edges a and b. In the left rectangle, the edges are inserted one at a time, first a, and then b. The influence set for each insert is highlighted in blue. Note that the star vertex is not influenced when a and b are inserted separately, but is influenced when a and b are inserted together. Challenge: Bounding the runtime. The runtime arguments of CZ and BDHSS do not transfer to the batch setting for technical reasons. We include a discussion in Section 8.2.
2.1
Our approach
Our approach involves (1) defining an influence-analysis version of R-LFMIS, (2) proving that for b unknown inputs this version has a batch influence set of expected size at most b, (3) relating this directly to the vertices that can possibly change mark in a set of b edge insertions and deletions, (4) developing a generic algorithm that operates either sequentially or in parallel for propagating changes through the graph, (5) bounding the work of this propagation, and (6) bounding the depth. We outline these steps here. (1) We first define an “influence analysis” version of R-LFMIS where one is given a graph along with an arbitrary subset of its vertices and edges marked as “undecided”, indicating that we do not know if they are present or not. It outputs a set of “influenced” vertices for which we consequently might not know if they are in the MIS or not. The set of influenced vertices can be identified using a modified version of the greedy R-LFMIS algorithm. As in LFMIS, the algorithm iterates through the vertices in π order, skipping vertices that are eliminated. When processing a vertex v that is known to be in the graph (not in the undecided set, and hence in the MIS), the algorithm eliminates any neighbors of v across decided edges (as with R-LFMIS), and marks any neighbors of v across undecided edges as undecided (we do not know if they are eliminated). When the algorithm processes a vertex v that is undecided, it does not know if v exists and hence whether it is in the MIS. Therefore, it adds v to the influence set and marks all its neighbors as undecided (since, again, we do not know if they are eliminated). The vertex v and incident edges are eliminated (as with R-LFMIS). See Figure 4 for an example of how a graph changes in response to a step of influence analysis. We only use this algorithm for analysis, we never run it. (2) To analyze the size of the influenced set, it is relatively straightforward to show that any expansion of uncertainty to neighbors is offset in expectation by the consumption of undecided edges or the elimination of other undecided edges and vertices. We then use this conservation to show that for the b undecided edges and vertices at the start, the expected total size of the influence set I at the end is ≤ b (roughly, each step never grows the expected sum of b + |I| and b = 0 at the end). We believe that even in the single update case, this influence analysis proof is arguably 6
?
v
?
v
?
Figure 4: Our batch influence set propagation. The question marks indicate undecided vertices and edges before processing the next vertex v. Both images show different cases for processing vertex v depending on whether it is undecided (left) or not (right). The colors indicate the states after processing v: pink means influenced, red means eliminated, and blue means undecided. The left shows the case where v is an undecided vertex; when processing v, v joins the influence set (pink), its two incident edges are removed (red), and both its neighbors become undecided (blue). The right shows the case where v is not undecided. Here its bottom neighbor is eliminated because it is connected by a not-undecided edge, but its right neighbor becomes undecided because the connecting edge is undecided. simpler and more intuitive than the original proof. (3) Similar to CHK, we note that for a vertex to begin marked and end unmarked, an earlier neighbor (or new neighbor from insertion) must end marked, and for a vertex to begin unmarked and end marked, all earlier marked neighbors must have unmarked (or have been disconnected via deletion). If the influenced set is a superset of all vertices before v that change mark, v will also join the influence set if necessary; therefore by induction the influence set includes the earlier neighbors that change mark. (4) Although the batch influence set is a great analysis tool, using it as our algorithm would be too slow. For our actual algorithm, we assign to each vertex an elimination time, which is the permutation time of its earliest marked neighbor, or its own permutation time if no earlier neighbor is marked. Our generic parallel algorithm then operates by repeating the following: find all conflicts in the graph (wherever there is a vertex with an incorrect elimination time), choose a subset of the vertices causing these conflicts, and fix the conflicts caused by that subset. We get a work-depth tradeoff based on how we choose the subset. The correctness of this algorithm follows from the fact that we keep iterating until all conflicts are removed, that a set of marked vertices without conflicts is necessarily the LFMIS, and that our algorithm makes progress on every step and therefore terminates. (5) At a high level, the efficiency argument proceeds as follows. First, we show that the work of the algorithm is bounded by the remaining 2-hop neighborhood of each vertex in the influence set (at the permutation time of that vertex). This corresponds to the neighbors (and neighbors of neighbors) we access looking for a replacement edge when a vertex’s eliminator leaves, as well as the cost of updating our out-edge structure. Then, using our batch influence set, we will show that the sum of the 2-hop neighborhood sizes is O(b log2 n log ∆). In order to bound our work by the 2-hop neighborhood size of influence set vertices, we process influenced vertices in O(log3 n) shells (permutation time ranges). By fully processing earlier vertices before later vertices, we ensure that we do not access many out-neighbors of any vertex in later shells. We use O(log3 n) shells so that each vertex has a low probability of sharing a live neighbor in its shell. Note that influence set vertices can be repeatedly marked and unmarked (see Figure 5), and that a given vertex can be processed a superconstant number of times. However, if we process by shells, and a vertex has no neighbors in its shell, we will only process that vertex once. Thus, we will only redundantly process a few vertices, fixing our work bounds. 7
w
w
w
w
Figure 5: Example of repeating processing of a vertex. In response to the edge insert (dotted), we show selected snapshots from the graph as propagation occurs. Note that vertex w will be repeatedly marked and unmarked as we update its neighbors. In some graphs, we could process the same vertex O(log n) times. To avoid this when possible, we separate vertices into shells, and process different shells separately. To show that the expected sum of the size of the 2-hop neighborhoods is O(b log2 n log ∆), we first prove that a step i < n/4 of R-LFMIS has roughly a nbi2 chance of contributing a vertex to the 2
n 2 b log n influence set, which will then pay O(( n log ) contribution i ) ) cost. Then we have expected O( i per step, which leads to the desired bound. Note that steps where i ≥ n/4 are inexpensive because the degree of the surviving graph is O(log n) whp. The proof that each step i < n/4 has a low probability of contributing to the influence set informally proceeds as follows. As before, the expansion of uncertainty to neighbors is offset by the maybe vertices being eliminated. Because there is a (roughly) nb chance a batch edge will be selected, causing a vertex to join the undecided vertex set, the expected size of the undecided vertex 1 set is roughly upper bounded by bi n . Since an (alive) undecided vertex has a n−i chance of being chosen in step i, we get the probability nbi2 . (6) For our depth bound, we argue that the number of rounds we need to process a shell is bounded by the dependence depth of the graph, which is O(log n) whp. Our overall depth then becomes O(log5 n) by (pessimistically) multiplying all of the following: we have O(log3 n) shells (empty shells are skipped, but for the depth bound we apply the pessimal bound); each shell takes O(log n) rounds to process; each round uses parallel primitives whose depth is O(log n) even for large batches.
3
Preliminaries
Parallel model. We assume the binary fork-join model [16]. In this model, a process can spawn two new processes with a fork, which can operate independently, and later join together when finished. The model permits concurrent writes; in particular, if two threads try to write a and b concurrently to the same variable, an arbitrary choice of a and b will be written. Nested parallelism is permitted: these new processes can themselves spawn more processes. The work of a computation is the total number of operations required across all processors, and the depth is the longest chain of dependent instructions. We permit the atomic operations test and set (TS) and compare and swap (CAS), which are only used in our parallel primitives. We note that the work is robust across models: permitting randomization, the work of an algorithm in the binary fork-join model is the same asymptotically as the work in the arbitrary way fork-join model and as the work in the CRCW PRAM, and the depth of an algorithm is within a O(log n) factor of the depths in the arbitrary way fork-join and CRCW PRAM [16]. We thus care about optimizing the work: optimizing the depth is not a focus in this work.
8
To simplify our pseudocode, the pseudocode includes an atomic write minimum operation. This can be easily implemented under the hood with a semisort, for more details see Section 8.1. Parallel primitives. We will use various standard parallel operations. Given an array, a scan (also known as prefix sum), will return a running sum of the associative operator f on the first i elements of the array. A scan can be used to implement a filter, which given a boolean function and an array, returns an array of the elements for which the function returns true. A scan can also be used to give a flatten, which given an array of arrays, returns a single array of all of the elements. Scan, filter, and flatten all take O(n) work and O(log n) depth [38]. Given an array of elements, a semisort will return an array such that elements with the same key are consecutive (though elements with different keys not sorted from least to greatest). Semisort requires O(n) expected work and O(log n) depth whp [16, 34]. A bag data structure supports appending elements, deleting elements (given a pointer), returning the number of elements present, and outputting b (arbitrary elements) of a container. A bag does not support membership queries and is unsorted. Recent work developed a bag that supports a batch of b element updates in O(b) work and O(log b) depth [14], and that can output b elements in O(b) work and O(log b) depth. Batch-Dynamic model. In the batch-dynamic model, edge updates arrive in discrete (integer) time steps. At time t, a batch Bt of edge insertions and deletions arrive and are applied to the old graph Gt−1 , yielding the new graph Gt . In response to this batch of edges, we must update the MIS. At time t, we must have an MIS for the graph at Gt : each vertex must know whether it is marked or unmarked, and we must hold a bag containing all marked vertices. The edge updates are being given by an oblivious adversary, which knows our algorithm but not our randomness, and must commit to an entire update sequence at the beginning of time. The update sequence is revealed to the algorithm by time step (at time t, the algorithm does not know what the edge updates for time t + 1 will be). We note that the oblivious adversary is a standard assumption for dynamic MIS [19, 12]. MIS and LFMIS. Formally, the set M is a maximal independent set (MIS) iff the following conditions hold: 1. If u ∈ M , then N (u) ∩ M = ∅ (no adjacent marked neighbors), where N (u) is the neighbors of u. 2. u ̸∈ M , that there exists v ∈ M ∩ N (u). We call vertices in the MIS marked, and vertices not in the MIS unmarked. A natural static algorithm for finding an MIS is the lexicographically first, or greedy, approach. The vertices are given an arbitrary order π. We call π(v) the permutation time (or π-value) of v. We iterate through this order. If a vertex has been eliminated, we continue iterating, and do not add the vertex to the MIS. Otherwise, we add the vertex to the MIS, then eliminate it and its neighbors. This is called the lexicographically first MIS (LFMIS). When π is chosen uniformly at random, the resulting MIS is called the R-LFMIS. Given a set M , one can verify that it is the LFMIS without iterating, by verifying that every marked vertex has no marked neighbors and every unmarked vertex has an earlier marked neighbor, for details see Section 8.3. Dependency Graph. Traditionally in an LFMIS, let the deletion time be the permutation time at which a vertex marks or is eliminated [17]. Then, the dependence graph is an orientation of 9
3 Increasing Elimination Time
1
2
4 5
Increasing π-value
Figure 6: Example graph, marked vertices are shaded red. In this example, vertex 5 has later π-value than vertex 3 but earlier deletion time, so we orient the edge from 5 to 3, not the other way around. the graph by the deletion time (low to high). In the event of tied deletion time, a marked vertex points to an unmarked one. If both are unmarked, then the vertex with lower permutation time points to the higher. Note that a vertex v’s out neighbors are those present when v is eliminated from the graph. In this way, a dependency graph nicely captures how a graph shrinks over time. Note that the dependency graph is not an orientation by π-ordering. If a vertex with late π value is eliminated early, it will have many out neighbors, as shown in Figure 6. Parallel static MIS. Note that the LFMIS can be computed in parallel, where each vertex that has the local highest priority of its surviving neighbors marks and eliminates its neighbors. Blelloch, Fineman, and Shun [17] showed that when iterating the R-LFMIS and removing eliminated neighbors, the graph shrinks in degree quickly, as expressed by the following lemma.6 Lemma 3.1. Let π be a random order of the vertices, and suppose we have iterated through the first i − 1 vertices (marking if alive, and eliminating neighbors of marked vertices). Then the remaining n graph has max degree O( n log i ) whp [17]. The number of rounds required by parallel R-LFMIS is equal to the length of the longest alternating eliminator path (AE-path). An alternating eliminator (AE)-path is a marked-unmarked alternating path of increasing π where the marked-unmarked edges are eliminator-target pairs.7 Blelloch, Fineman, and Shun showed that the longest AE-path has O(log2 n) length whp [17], which was improved to O(log n) whp by Fischer and Noever [27].
10
Symbol V? E? Vi? Ei? π Vil F M Vi M (G)
Meaning undecided vertices undecided edges undecided vertices, before iteration i undecided edges, before iteration i chosen permutation on the vertices vertices not in π[1 : i) shorthand for InfluenceMIS the R-LFMIS, before the edge updates alive vertices before iteration i The LFMIS for G (with order π)
Table 1: Notation for influence analysis.
4
Influence Analysis of MIS
The influence analysis version of a function determines which outputs are undecided given that some inputs are undecided. More formally, for deterministic problems (i.e. functions) taking sets to sets, we define it as follows. Definition 1. Consider a deterministic problem P : P(I) → P(O). The influence analysis problem for P is given an input I ⊆ I and an undecided subset I ? ⊆ I, to determine the undecided (influenced) outputs O? = {o ∈ O | ∃I x ⊆I ? s.t. o ∈ (P (I \ I x ) △ P (I))}. Looking forward to its application to dynamic algorithms, note that influence analysis makes no distinction between insertion and deletion of elements: the set I includes all input (i.e. the input with the inserts added but without the deletes removed), and I ? will include both inserted and deleted elements. A conservative solution to an influence analysis problem is one that reports back all the undecided output elements, but might include some extra elements. Note that returning all elements is a vacuously conservative solution; we want to find a conservative solution with small size. We note that influence analysis is loosely related to the sensitivity analysis of boolean functions and stability analysis [3, 47]. In our case, the source problem P that we care about is LFMIS. The input of the influence analysis problem for LFMIS is a graph G = (V, E) and an undecided set of vertices V ? ⊆ V and edges E ? ⊆ E. If a vertex is undecided, it means that it together with its incident edges in G are either present or not. The problem is to determine which outputs (members of the MIS) are 6
By iterating, we mean stepping through the vertices and adding them to the LFMIS if possible. Concretely, suppose we have processed the first i − 1 vertices, and removed all the neighbors of vertices we marked. BFS showed that the maximum degree in this remaining graph is small whp. 7 An AE-path was called a dependency path in Fischer-Noever. Note that we differ from Fischer-Noever in allowing the path to start with an unmarked or a marked vertex; note that this alters the path length by at most 1, and so their results still apply within constant factors. We prefer the name AE-path to clarify that we are not trying to bound the length of any path in the dependency graph, but only paths that cause a bottleneck for R-LFMIS. In particular, unmarked vertices can have harmless directed edges between them, and these will not appear in an AE-path
11
1 InfluenceMIS(G = (V, E), V ? ⊆ V , E ? ⊆ E, i) 2 if V ? = ∅ and E ? = ∅ : return ∅ 3 u = π(i) 4 if u ∈ /V : 5 return InfluenceMIS(G, V ? , E ? , i + 1) 6 if u ∈ V ? 7 foreach v ∈ NG (u) : add v to V ? 8 delete u from G, V ? , E ? 9 return {u} ∪ InfluenceMIS(G, V ? , E ? , i + 1) 10 else 11 foreach v ∈ NG (u) : 12 if (u, v) ∈ E ? : add v to V ? 13 else : delete v from G, V ? , E ? 14 delete u from G, V ? , E ? 15 return InfluenceMIS(G, V ? , E ? , i + 1)
Figure 7: Conservative algorithm for the influence analysis problem for LFMIS. The algorithm returns a (possible overestimate) of all vertices that might be influenced by the undecided inputs. V1 is the original set of vertices in some ordering π. Eliminating a vertex from a graph removes it and its incident edges. Removing u from E ? removes any edges from E ? that include u. influenced by the undecided vertices and edges. Figure 7 presents a variant of greedy MIS that conservatively solves the influence analysis problem for LFMIS. Throughout the paper, we will use Gi = (Vi , Ei ), Vi? , and Ei? to indicate the values of G = (V, E), V ? , and E ? at the beginning of step i. Note that counting the iteration number (i) will become helpful in proving the efficiency of our parallel algorithm in Section 6, but is not needed for the results in this section: from the view of this section, we could have defined influence propagation in purely recursive terms. Lemma 4.1. If u ∈ V ? , then u ∈ V (all undecided vertices are alive). Proof. By construction. Each place in our code where we remove a vertex v from V ? , we also remove v from the graph. Therefore, any undecided vertex is still alive. Lemma 4.2. The algorithm InfluenceMIS conservatively solves the influence analysis problem for LFMIS based on the ordering given by π. Proof. The proof is by induction on graph size. The inductive hypothesis is that the lemma holds on the smaller graph, assuming that V ⊆ {Vπ (j) : j ∈ {i...n}}, i.e., we will visit all vertices. We note that all steps maintain V ⊆ {Vπ (j) : j ∈ {i...n}} since advancing i always removes Vπ (i) from the graph. For the base case where nothing is undecided, it correctly returns the empty set. For the inductive case, we consider the subcases. We can ignore steps where u ∈ / Vi since they do not do anything beyond advancing i. If u is undecided, then it may or may not appear in the MIS depending on whether it is present or not, and we therefore include it in the influenced outputs. Furthermore, since we do not know whether u is there, we also do not know whether it will eliminate its neighbors in R-LFMIS. Therefore, the neighbors become undecided (note that some could already be undecided). No other vertices become undecided, so when making the recursive call and assuming its result is correct by induction, it will return all influenced vertices. If u is 12
not undecided, then it will always be added to the MIS and therefore not returned as influenced. Furthermore, since u is added to the MIS, any neighbors through decided edges will be eliminated, and any neighbors through undecided edges might or might not be eliminated. Again, assuming that the recursive call is correct by induction, the final result will include all influenced vertices. We note that the algorithm might return vertices that will always be in or out for all possible settings of V ? and E ? . In particular, if a vertex v gets added to V ? twice (or more), then it is possible that the two vertices that add v always have the opposite parity (one is in if the other is out), and hence v will never be in the MIS (one such example is vertex 5 in Figure 2). Furthermore, if v adds an adjacent u to V ? , the vertex u could be returned as influenced even though u will always be in the MIS. In the following, however, we show that the influence set is small in expectation. We note that the influence set of CHK also contained vertices that would be definitely in or out of the R-LFMIS. We add some notation. Let Π(V1 ) be the set of all possible permutations of all vertices. Let Πi (V1 ) be the set of all possible permutations, given that the vertices in permutation positions [1, i) are fixed to some value. Let Vil denote the vertices for which permutation values have not yet been assigned, before a vertex has been chosen for permutation position i. Let Vi? denote the undecided vertices after iteration i, and Ei? the undecided edges after iteration i. We use F as a shorthand for InfluenceMIS. Lemma 4.3. Let G, V1? , E1? be the starting graph and undecided vertices and edges. Let G, V ? , E ? be a possible state of the graph and undecided sets immediately before iteration i. Let π[1 : i) be a possible prefix of a permutation that would lead to this graph state. Consider F (G, V ? , E ? , i), and let F (G′ , V ′? , E ′? , i + 1) be the resulting recursive call. Let Πi be the set of permutations that could result in G, V ? , E ? from the given starting state, given that π[1 : i) is fixed. Draw π uniformly at |V ? | random from Πi . Then Eπ∼Πi [|V ′? | + |E ′? |] ≤ |V ? | + |E ? | − n−i+1 . Proof. Consider the choice of u = π(i). Note that for any permutation X ∈ Πi , any ordering of the vertices in Vil would have been in Π. Therefore, the choice of u is uniformly random among the unchosen vertices. Note that if u ̸∈ V , then we iterate i without changing the graph. Instead of taking a vertex-centric perspective, viewing the neighbors that are added or removed from the undecided set due to picking a particular vertex, we take an edge-centric view on the change. We break down the change in |V ? | + |E ? | to three factors: that a chosen vertex in V ? removes itself, the removal of undecided edges when an endpoint is picked, and that an edge can remove/add one of its endpoints. We thus have that E[|V ′? | + |E ′? | − |V ? | − |E ? |] = −
u∈V
+
X 1 2 − n − i + 1 n − i+1 ? ?
X
X
e∈E
2 + n−i+1 ?
(u,v)∈E u,v̸∈V ?
≤
X (u,v)∈E ? u∈V ? ,v̸∈V ?
1 n−i+1
−|V ? | n−i+1
We explain this equation in more detail. First, the expected effect on |V ′? | + |E ′? | of a vertex ?| −|V ? | removing itself is n−i+1 . Similarly, the expected change in the size of E ? is −2|E n−i+1 . For two vertices 13
2 chance of selecting one and adding u, v not in the undecided set where (u, v) ∈ E ? , there is a n−i+1 the other to the undecided set. For two vertices u, v where u ∈ V ? but v ̸∈ V ? and (u, v) ∈ E ? , 1 there is a n−i+1 chance of picking u, causing v to be added to V ′? . Note that a decided edge with 1 1 only one endpoint in V ? has a n−i+1 chance of adding one vertex to V ? , and a n−i+1 chance of ? ? ? removing one vertex from V , for a net zero change in |V | + |E |. Thus the overall expected change in |V ? | + |E ? | (compared to |V ? | + |E ? |) is upper bounded by −|V ? | n−i+1 . Note that when there are undecided edges between undecided vertices, the expected change ?
−|V | in |V ? | + |E ? | is at most n−i+1 .
In the above lemma, we have shown that the total number of undecided vertices and edges shrinks over time in expectation. In the next lemma, we will show that the growth of the influence set is balanced by the shrinking of the undecided set, and so the size of the influence set is nicely bounded. Lemma 4.4. For π drawn uniformly at random from all permutations of V , we have that: Eπ∼Π(V ) [|InfluenceMIS(G, V ? , E ? , i)|] ≤ |V ? | + |E ? | Proof. We proceed with induction. Base Case 1: Suppose that for some i, we have that |V | ≤ |V ? |+|E ? |. By construction, the amount that can still be added to the influence set is no more than |V |, so F (G, V ? , E ? , i) ≤ |V ? | + |E ? |. Base Case 2: Suppose that for some i, V ? and E ? are empty. Then no more is added to the influence set, so F (G, V ? , E ? , i) ≤ 0 = |V ? | + |E ? |. Inductive Hypothesis: Let j ≥ i + 1. Let π[1 : j) be any prefix of a permutation that would yield G, V ? , E ? after j − 1 iterations. Let Πj be the set of possible permutations of V with π[1 : j) fixed, and suppose that π ∼ Πj . Then we have that Eπ∼Πj [F (G, V ? , E ? , j)] ≤ |V ? | + |E ? |. Inductive Step: Now consider Eπ∼Π [F (G, V ? , E ? , i)]. Let G′ , V ′? , E ′? denote the graph and undecided sets resulting from choosing a vertex u. We condition the expectation on the choice of the next vertex u. Observe that Eπ∼Πi [F (G, V ? , E ? , i)] =
1 |V ? | Eπ∼Πi |π(i)=u [F (G′ , V ′? , E ′? , i + 1)] + . n−i+1 n−i+1 l
X
u∈Vi
Because we have fixed a prefix of the permutation of length i, we can apply the inductive hypothesis to get that Eπ∼Πi+1 [F (G′ , V ′? , E ′? , i + 1)] ≤ |V ′? | + |E ′? |. Plugging back into our main equation yields Eπ∼Πi [F (G, V ? , E ? , i)] =
X |V ? | 1 + (|V ′? | + |E ′? |) n−i+1 n − i + 1 l u∈Vi
=
|V ? | n−i+1
+ Eu∈V l [|V ′? | + |E ′? |] i
?
?
|V | |V | which by Lemma 4.3 is upper bounded by |V ? |+|E ? |− n−i+1 + n−i+1 = |V ? |+|E ? | as desired.
14
4.1
Connecting influence analysis to R-LFMIS
We now want to relate the influence analysis problem for LFMIS to the dynamic algorithm for the problem. In this paper, we only care about adding and removing edges. As before, we define Vi and Vi? to be the states of V and V ? at the beginning of the ith call to InfluenceMIS. Let M (G) be the LFMIS on a graph G for a permutation π that is clear from context. Let Enew = E ∪ E+ \ E− , Gnew = (V, Enew ), Eall = E ∪ E+ , Gall = (V, Eall ), and I = InfluenceMIS((V, Eall ), ∅, E+ ∪ E− , 1) Lemma 4.5. If vertex u = π(i) ∈ Vj? for some j ≤ i, then either u ∈ Vi? or u ∈ / Vi . Proof. The claim is true if no predecessors modify u’s placement after iteration j. Suppose w = π(k), j < k < i is a predecessor of u. The only way for w to remove u from V ? is to also remove u from V . Lemma 4.6. Let G = (V, E) be a graph, and suppose we run InfluenceMIS on an input graph Gall = (V, E ∪E+ ) and E ? so that E ? contains the batch updates. If vertex u = π(i) and u ∈ Vi \Vi? , then u ∈ M (G). If u = π(i) and u ∈ / Vi , then u ∈ / M (G). Proof. By induction on the π value of u. The base case is that u = π(1). Vertex u will always be in V1 and marked regardless of the arrangement of edges. Assume now that it is true for all vertices in π[1, i − 1]. Let π(u) = i. Suppose u ∈ Vi \ Vi? , and consider a predecessor w = π(j) of u in G. Suppose for contradiction that w ∈ Vj \ Vj? . Then w either removes u from V (if (w, u) ̸∈ Ej? ) or adds u to Vj? (if (w, u) ∈ Ej? ). The first case contradicts that u ∈ Vi . In the second case, by Lemma 4.5, we have that either u ∈ Vi? or u ∈ / Vi , contradicting u ∈ Vi \ Vi? . Therefore, w ̸∈ Vj \ Vj? . Suppose for contradiction that w ∈ Vj? . Then w adds u to V ? , and by Lemma 4.5, we have that u ∈ Vi? , contradicting u ∈ / Vi? . Therefore, w ∈ / Vj? . Thus u only has predecessors (in G) of the form w = π(j) such that w ∈ / Vj . By the inductive hypothesis, w ∈ / M (G). Therefore, u is not eliminated by any predecessor in G, and is in M (G). Suppose now that u ∈ / Vi . Then u is eliminated from V by some predecessor w = π(j) ∈ Vj \ Vj? . Furthermore, (w, u) must exist in G because (w, u) is not an undecided edge. By the I.H., w ∈ M (G), thus u ∈ / M (G). Lemma 4.7. If u = π(i) ∈ M (G) and u ∈ Vj? for some j < i, then u ∈ Vi? . Proof. The contrapositive of Lemma 4.6 indicates that u ∈ M (G) =⇒ u ∈ Vi . The vertex u cannot be removed from V ? during some iteration k > j without also permanently removing u from V , so it must be the case that u remains in V ? until the beginning of iteration i. Lemma 4.8. Consider LFMIS applied to graphs G = (V, E) and Gnew = (V, Enew ). We have M (V, E) △ M (V, Enew ) ⊆ InfluenceMIS((V, Eall ), ∅, E+ ∪ E− , 1) Proof. By induction on the π values of each vertex. We claim that for vertex u with π(u) = i, if u ∈ M (G) △ M (Gnew ), then u ∈ I. Base case: For π(u) = 1, u will always be marked regardless, thus u is not in the left-hand side. Inductive case: Assume that the claim holds for all vertices ∈ π[1, i − 1]. We want to show that the claim holds for π(u) = i.
15
Case 1: u = π(i) is a vertex in M (G) \ M (Gnew ). Either a predecessor w of u in Gnew flips to marked (and (w, u) exists in both the old and new graph), or a new predecessor w of u is connected to u via insertion so that w is marked in Gnew and eliminates u. Case 1a: Some predecessor w = π(j) of u in G flips to marked. By the I.H., w ∈ I, which moreover implies that w ∈ Vj? . It must be the case, then, that w adds u to V ? . By Lemma 4.7, u ∈ Vi? , and thus adds itself to InfluenceMIS during iteration i. Case 1b: No predecessor of u in G that flips to marked, and instead a new predecessor w = π(j) of u is connected via insertion so that w is marked in the new graph and eliminates u. If w ∈ M (G), then w ∈ Vj by Lemma 4.6. Since (w, u) ∈ Ej? , u is added to Vj? . On the other hand, if w ∈ / M (G), then w ∈ M (Gnew ) \ M (G), and by the inductive hypothesis, w ∈ I, i.e., w ∈ Vj? . Because we run InfluenceMIS on Gall consisting of all edges in either G or Gnew , w adds its new neighbor u to V ? . In either case, because u is added to V ? by some vertex with an earlier permutation time than u, by Lemma 4.7, u ∈ Vi? , which results in u adding itself to InfluenceMIS during iteration i. Case 2: u = π(i) is a vertex in M (Gnew ) \ M (G). Because u ∈ / M (G), by Lemma 4.6, u ∈ / Vi \ Vi? . Therefore, to guarantee that u ∈ I, we need only show that u ∈ Vi . We prove this is true by contradiction. Suppose u ∈ / Vi . Then there must be a predecessor π(j) = w ∈ Vj \ Vj? that eliminates u from V during the influence analysis. By Lemma 4.6, w ∈ M (G). If (w, u) is an undecided edge, then w adds u to V ? and fails to remove u from V . Otherwise, because u ∈ M (Gnew ), we have w ∈ / M (Gnew ), so w ∈ M (G) \ M (Gnew ). By the I.H., w ∈ I, which ? can only occur if w ∈ Vj , which contradicts that w ∈ Vj \ Vj? . Because both cases lead to contradiction, u ∈ Vi , hence u ∈ I.
Corollary 4.8.1. For a graph G, the expected recourse for a set of b edge updates (mix of insertions and deletions) is at most b. Proof. Note that the recourse in batch-dynamic MIS is the symmetric difference of the MIS before and after the edge update. By the above lemma, the symmetric difference of the R-LFMIS before and after the edge updates is bounded by the size of the influence set, which by Lemma 4.4 is bounded by b.
5
Algorithm
5.1
Data Structures
We will store the graph oriented by elimination time. In this section, we will write u to denote the vertex u, as well as its permutation time π(u). We use the comparator <π to emphasize that we are comparing permutation times: u <π v means that π(u) < π(v). We write l(u) for the elimination time of a vertex. The graph will be oriented from least to greatest, according to the value of the pair (l(u), u), as shown in Figure 6. When we compare (l(u), u) to (l(v), v) we first compare l(u) and l(v), then tiebreak on u and v if l(u) = l(v). 16
In the following pseudocode, the vertex names (e.g. u, v, w) indicate their ordering in the permutation. The variable l(u) maintains the deletion time of vertex u: if l(u) =π u then u is in the MIS The variable O(u) is true if u used to be in MIS (one round before) Assume edges are directed , where u → v if (l(u), u) <π (l(v), v). N h (u): out edges of form u → v where u <π v N l (u) : out edges of form u → v where u >π v N + (u) = N h (u) ∪ N l (u) N − (u) : the in edges stored as log n bags, the ith bag stores π−values in range [2i , 2i+1 ) N − (u, v) : fetch the in edges w of u such that w ≥π v 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
lower v to u: N ← N − (v, u) writeMin(l(v), u) if (l(v) = u) : parfor w ∈ N : orient(v, w) if O(v) : enque(Q, (v, −)) raise v from u: N ← N l (v) ∪ N h (v) t(v) ← findReplacement(v) l(v) ← t(v) parfor w ∈ N : orient(v, w) if l(v) =π v : enque(Q, (v, +)) findReplacement(v) : R ← {w ∈ N l (v) | l(w) =π w} if R = ∅ : return v // no replacement else return min(R) orient (v, w) : if (l(v), v) <π (l(w), w): v → w else : w → v
23 propagate(E+ , E− ) : 24 empty Q 25 L ← {{u, v} ∈ E+ , u <π v | O(u) ∧ l(v) >π u} 26 parfor {u, v} ∈ L: lower v to u 27 28 L ← {{u, v} ∈ E− , u <π v | O(u) ∧ l(v) =π u} 29 parfor {u, v} ∈ L: raise v from u 30 31 while Q ̸= ∅ : 32 A ⊆ Q, Q = Q \ A 33 parfor (u, +) ∈ A, : // lowering stage 34 if l(u) =π u : 35 O(u) ← true 36 parfor v ∈ N h (u) : lower v to u 37 38 parfor (u, −) ∈ A : // raising stage 39 if l(u) ̸=π u : 40 O(u) ← false 41 L ← {N h (u) | l(v) =π u} 42 parfor v ∈ L : raise v from u
Figure 8: Our Parallel Change Propagation Algorithm. Given a set of edges E+ to insert and a set of edges E− to delete, the algorithm updates the R-LFMIS. The runtime efficiency of the algorihtm depends on how A is picked. If A is the single minimum π-value vertex in the queue, then we get a sequential algorithm. If we pick A = Q, we get a maximally parallel algorithm, with lower depth but slightly higher work. If pick all up to some cutoff (a single shell), then we get our main algorithm. Symbol u l(u) <π Q A
Meaning the vertex u, also its permutation time π(u) elimination time of vertex u comparator on permutation time conflict queue subset of conflict queue Table 2: Notation used in Section 5. 17
We will keep track of the following quantities per vertex. Each vertex has three types of neighbors: in neighbors, out higher neighbors, and out lower neighbors. For an edge (u, v), u is an in neighbor of v if (l(u), u) < (l(v), v). The vertex u is an out (higher) neighbor of v if (l(u), u) > (l(v), v) and u > v. The vertex u is an out (lower) neighbor of v if (l(u), u) > (l(v), v) and u < v. For a vertex v, we denote the in neighbors by N − (v), the out higher neighbors by N h (v), and the out lower neighbors by N l (v). In neighbors are sorted into log n bags of doubling range (of elimination times), and unsorted within each bag. The ith bag contains the in neighbors with elimination times in range [2i , 2i+1 ). Out lower, and out higher, neighbors are unsorted. A vertex holds the in-edge bags in an array of length O(log n). The first time that we insert an edge adjacent to endpoint v, we initialize this array, which takes O(log n) work.
5.2
Algorithm
We give pseudocode for our algorithm in Figure 8. Recall that our program is operating in synchronized lock step (i.e. joins after each line). Helper functions. Given a set of pairs (j, i), the lower j to i routine (lines 1-6) will do the following (to all pairs, in parallel). The new elimination time (level) for j will be set to the minimum of the i’s that are lowering it (line 3). Then, some of j’s edges will be flipped to correspond to the new elimination time (line 5). If j was previously marked, then we add it to the queue, so that it can propagate changes to its neighbors (line 6). Given a set of vertices (j), the raise j from u routine (lines 8-13) will do the following (in parallel lock step). The vertex j will search for a replacement eliminator (earlier marked vertex) (line 10). If one is found, the minimum such vertex (line 18) will be assigned as j’s new elimination time (line 11). Otherwise, j will mark (line 11), and join the queue to propagate changes to its neighbors (line 13). Some of j’s edges are flipped to account for its new elimination time (line 12). Main Algorithm. Given an insert edge batch E+ and a deletion edge batch E− , we do the following. For the insertion batch, we find all adjacent marked neighbors, and lower the later neighbor (lines 25-26). For the deletion batch, we find all update edges where the earlier end is marked and eliminates the later unmarked endpoint, and we raise the later endpoint (lines 28-29). Our queue8 may now contain vertices that must trigger changes in their neighbors. While the queue is nonempty, we take a subset A of the queue to process. We remove A from the queue. Then, for the vertices which previously marked, we lower their neighbors (lines 33-36), and for the vertices that previously unmarked, we raise their eliminated neighbors (lines 38-42). Regardless of the subset we pick, our algorithm is correct (see Section 5.3). However, the subset we choose affects our work and depth bounds. Roughly speaking, the more vertices we choose, the more parallel our algorithm is, but we may do redundant work as a result. Note that we get a sequential algorithm at a high-level similar to BDHSS when we choose a single vertex, the minimum permutation time vertex, to process each round. 8 Technically, the vertices that we are processing are stored in an array of bags, one per shell, not a queue. We refer to this structure as a queue for intuition, because in the sequential case it would be a priority queue.
18
5.3
Correctness
In this subsection, we will show the correctness of our algorithm. First, we will show that we correctly maintain the oriented graph on the edges. Assuming that our orientation is correct, we show that our queue will contain all of the information necessary to fix our R-LFMIS. We then show that we make progress in every iteration, and so our algorithm is correct. Maintaining a correct orientation. Recall that we say that a graph orientation is correct according to π if for all edges (u, v), we have that u → v ⇐⇒ (l(u), u) <π (l(v), v). In this subsection, we will show that we maintain a correct graph orientation, between each lowering and raising stage. Whenever we call the orient function (lines 20-22), we correctly fix the edge called on. For efficiency reasons, we do not call orient on every edge incident on a vertex when we change its elimination time, only edges that may actually flip direction. We show that we call orient on the necessary edges to fix the orientation. Lemma 5.1. Consider a set of calls lower(vi , ui ), where ui < vi . These calls maintain a correct graph orientation. Proof. Within the call to lower, each v : (u, v) (where u <π v) has its elimination time potentially modified. Of the edges (ui , v), the smallest ui will win the writeMin and set the elimination time of vi to ui . Denote a vertex’s original elimination time by l(x) and new elimination time by l′ (x). We must show that all neighbors of v with new elimination time in the range [ui , l(v)] have an orient call. First, note that lower v to ui will call orient on all edges with neighbor originally in range [ui , l(v)]. Now consider a neighbor w of v with l′ (w) ∈ [ui , l(v)] but l(w) ̸∈ [ui , v]. Since lower only reduces elimination time, we have l(w) > l(v), and so v was an in-neighbor of w. Then w had its own lower call to a value l′ (w) ∈ [ui , v]. Since w’s lower call will check all in-neighbors with elimination time originally in range [w′ , w] and l(v) ∈ [w′ , w], w’s lower call will orient (v, w). Therefore, all in neighbors of v in range [ui , l(v)] have an orient call. Lemma 5.2. Consider a set of calls raise(vi , ui ), where ui < vi . These calls maintain a correct graph orientation. Proof. Note that raise can only increase the elimination time of vi , and thus it suffices to only orient every (formerly) outgoing edge (v, w) ∈ N + (v), which raise does by orienting every edge to a neighbor in N (line 9). Lemma 5.3. At the beginning of each lowering/raising stage, the graph is oriented correctly. Proof. Note that whenever we call orient on an edge, we correctly direct the edge based on the elimination time. Furthermore, note that we change elimination times, then sync, then call orient (no interleaving of calls to orient and changes of elimination time). If we called orient on every edge where at least one vertex changed elimination time, then the result would follow immediately. However, for efficiency reasons, calling orient on all such edges is wasteful. What we need to show is that if we change the elimination time of u from t to t′ , that we call orient on all neighbors of u with elimination time in range t to t′ . After the step of initializing L and directly before using parfor to lower vertices in parallel, no vertices have had their elimination times nor edge orientations modified yet, so the dependency 19
DAG is correct. By the above lemmas, each lower and raise maintains the graph orientation. Because all elimination time changes are expressed with a lower or raise, the graph orientation is correct between each raising and lowering stage by induction. Maintaining the conflict queue. Suppose that we have assigned elimination times to every vertex (where l(u) ≤ u for all u). Recall that u is marked iff l(u) = u. There are two types of conflicts: 1. Too early conflicts: l(u) < u = l(x) (x’s elimination time is too early). 2. Too late conflicts: l(u) = u < l(x) (x’s elimination time is too late). Note that if there are no conflicts, then we have found the R-LFMIS. Thus, conflicts are pairs (u, x) (which are necessarily also edges in the graph). Note that x could have multiple too late conflicts, but only one too early conflict. Note that x could have a too early and too late conflict at the same time (which is fine because we do not raise and lower concurrently). In this subsection, we will show that our queue captures all conflicts currently present in our graph. Note that in our queue, we do not store (u, x), but only (u, +) (if u had marked) or (u, −) (if u had unmarked); we will show that this is all we need to store. Lemma 5.4. Suppose that (u, x) is a conflict where l(u) < u = l(x). Then calling raise x from u will resolve this conflict. Similarly, suppose that (u, x) is a conflict where l(u) = u < l(x). Then calling lower x to u will resolve this conflict. Proof. Raising x will increase its elimination time, so that u < l(x), fixing the conflict. Note that only one call to raise x can happen concurrently, so this will fix. Lowering x will reduce l(x) at least to u, if not lower (because of concurrent lower calls). Thus, l(x) ≤ u, so the conflict is fixed after the lower call. Once we have marked u, if we need to propagate changes to u’s neighbors, we want to add (u, +) to the queue. Similarly, if we unmark u and need to propagate changes, we want to add (u, −) to the queue. In this next lemma, we show that we actually add these values to the queue when necessary. Lemma 5.5. Consider the conflicts created by a lower v to u call (the pairs (v, w) where l(v) < v = l(w)). If any such conflicts occur, then (v, −) is added to the queue. Similarly, consider the conflicts created by a raise v from u call. If any such conflicts occur, then (v, +) is added to the queue. Therefore, any conflicts created by a lower or raise call correspond to an addition to the queue. Proof. Consider the lower v to u call. Reducing v’s elimination time could cause later neighbors of v to have an incorrect (too early) elimination time. For this to occur, v would need to be marked before the lower call, in which case O(v) would be true, and so v would be enqueued. Note that any neighbor w of v which now has an incorrect elimination time has a later permutation time than v, so we have l(v) < v = l(w). When there are concurrent lower calls, each of which would enqueue v, the winner (minimum u) will enqueue v.
20
Consider a raise v from u call. Increasing v’s elimination time could cause a later neighbor w of v to have an incorrect (too late) elimination time. For this to occur, v would need to mark (raise to l(v) = v), which would cause v to enqueue. Note that l(v) = v < l(w). Lemma 5.6. Processing (u, +) fixes all too-late conflicts involving u, and processing (u, −) fixes all too-early conflicts involving u. Proof. We will want to show that processing (u, +) fixes all too late conflicts, and processing (u, −) fixes all too early conflicts. First, consider (u, +) ∈ A, and let (u, x) be a too-late conflict, where l(u) = u < l(x). Note that u passes the l(u) = u check, and will call lower on all neighbors in N h (u), and since u < x we have that x ∈ N h (u), so we do call lower x to u. By Lemma 5.4, this does fix the conflict. Next, consider (u, −) ∈ A, and let (u, x) be a too-early conflict, where l(u) < u = l(x). Since u = l(x) and u < x, we have that in the raising round, x ∈ N h (u) and so we will raise x from u. By Lemma 5.4, this does fix the conflict. Lemma 5.7. At the beginning of the while loop and between each mark and unmark stage, for all too-early conflicts (u, x) we have (u, −) ∈ Q and for all too-late conflicts (u, x) we have (u, +) ∈ Q. Proof. At the beginning of propagate, the queue is empty, and only later batch endpoints can have conflicts. Running lower on the batch insertions will resolve all too-late conflicts involving inserted edges via Lemma 5.6. By Lemma 5.5, lowering (some of) the batch endpoints will correctly add the subset of these batch endpoints that cause conflicts to the queue. At this point in time, since edge deletion cannot create too-late conflicts, note that there are no more too-late conflicts in the graph. There are two (possibly overlapping) types of too early conflicts: those incident on an edge deletion (where the earlier endpoint was the old eliminator), and those adjacent to a batch insertion endpoint (where the batch insertion endpoint was the old eliminator). The latter type of conflict is reflected already in the queue. Let (u, v) be an edge deletion with a too early conflict. Necessarily u was marked. Then this edge (u, v) will join L, and so we will call raise on this vertex, fixing the conflict (by Lemma 5.6 and adding (v, +) to the queue if more conflicts are created (by Lemma 5.5). Note that raising vertices cannot create too-early conflicts. All too-early conflicts caused by edge deletions were processed, and all of the other too-early conflicts were already present in the queue. Therefore, all too-early conflicts in the graph are present in the queue. Note that the only too-late conflicts that can be (currently) present are those caused by raising the later endpoints of deleted edges, which were added to the queue by Lemma 5.5. Therefore, all too-late conflicts created were added to the queue, and so the queue is up to date with all conflicts. Now we will proceed inductively. Consider a vertex (u, +) ∈ A participating in the lowering. By Lemma 5.6, all too-late conflicts involving u are fixed, and by Lemma 5.5, all conflicts created by the lower calls are added to the queue. Similarly, for a vertex (u, −) ∈ A participating in the raising stage, by Lemma 5.6, all too-early conflicts involving u are fixed, and by Lemma 5.5, all conflicts created by the raise call are added to the queue. Proving Correctness. Knowing that our queue maintains the conflicts correctly, we can quickly conclude the correctness of our algorithm. Lemma 5.8. Given a strategy that selects at least one vertex every round, our algorithm terminates.
21
Symbol Yj Zj Gi ∆ b
Meaning n log n j n 2 min(∆2 , ( n log j ) )
remaining graph immediately before R-LFMIS step i maximum degree in the graph (union of old and new graph) size of update batch Table 3: Notation used in Section 6.
Proof. Consider the lexicographic ordering of all possible queue contents (writing out the contents from early to late vertex). Note that processing a vertex v increases the lexicographic order (of the entire contents of the queue). Because processing a vertex removes it from the queue, our lexicographic order gets later over time, and so we eventually terminate. Lemma 5.9. Our algorithm is correct (finishes with an R-LFMIS on the new graph), for any policy for choosing S that chooses at least one vertex each while loop iteration. Proof. Because we terminate, we end with an empty queue. Therefore, no vertex has a conflict, and so we have the R-LFMIS.
6
Efficiency
In this section, we will prove that our algorithm is efficient (has low work and depth). First, we describe how we choose the subset A (the subset of the queue we process each iteration). We will separate the vertices into shells by permutation value, and handle the shells sequentially (but in parallel within a shell). We will choose our shells such that a vertex is unlikely to have a neighbor within a shell, and so in expectation a vertex is only processed a constant number of times (compared to O(log n) times). P Then, we will show that the cost of our algorithm is bounded in expectation by O( v∈S Zv ), n 2 9 where Zv = min(∆2 , ( n log We conclude by using a modified version of the batch influence v ) ). P set analysis to directly bound O( v∈S Zv ) by O(log2 n log ∆).
6.1
Shells
Suppose that we handle the algorithm in shells (by permutation value), where the ith shell has size si = (1 + log12 n )i−1 . The first shell starts at permutation time 1, and for i ≥ 2 note that the ith P 2 shell starts at permutation rank pi = 1 + i−1 j=1 sj = 1 + log n(si − 1). These shells are mainly for n work analysis, but do affect the depth (for the worse). For notational convenience, let Yj = n log j n 2 and Zj = min(∆2 , ( n log j ) ).
Lemma 6.1. Observe that there are O(log3 n) shells, and that the largest shell has size O( logn2 n ). 9
Note that ∆ is the maximum vertex degree in the union of the old and new graphs.
22
Proof. Let k be the number of shells, i.e., the largest i such that pi ≤ n. n−1 Largest shell size. From pi ≤ n, we have 1 + log2 n(si − 1) ≤ n, so si ≤ log + 1 = O( logn2 n ). 2 n
Number of shells. Since pi = ((1 + log12 n )i−1 − 1) log2 n + 1, the condition pk ≤ n requires n−1 (1 + log12 n )k−1 ≤ log + 1 ≤ log2n2 n . Taking logarithms, 2 n (k − 1) · ln 1 + log12 n ≤ ln log2n2 n ≤ ln n.
Using ln(1 + x) ≥ x/2 for x ∈ (0, 1), we have ln(1 + log12 n ) ≥ 2 log1 2 n , so (k − 1) ≤
ln n = 2 log2 n · ln n = O(log3 n) 1/(2 log2 n) k = O(log3 n)
Lemma 6.2. Let v ∈ V with pi ≤ n/2. The probability that v has any (in or out) neighbor inside its shell in Gpi is at most O( log1 n ). Proof. Let v be in shell i, which starts at permutation rank pi and has size si . We know that the n number of surviving neighbors of v at rank pi is at most d ≤ c n log whp for some constant c by pi Lemma 3.1. Each surviving neighbor’s rank is uniform over the n − pi remaining positions, and the shell (excluding v) occupies at most si − 1 of these. By a union bound, Pr[v has a neighbor in its shell] ≤ d ·
cn log n si si ≤ · . n − pi pi n − pi
Substituting pi = 1 + log2 n(si − 1) and simplifying, si si cn log n 2cn log n 2cn · · , ≤ = 2 2 (n − pi ) log n 1 + log n(si − 1) n − pi si log n n − pi 4c 1 For pi ≤ n/2, we have n − pi ≥ n/2, giving a bound of log n = O( log n ).
Lemma 6.3. Let v ∈ V where π(v) ≥ n/2. Then the probability that v has any (in or out) neighbor in its shell in Gπ(v) is at most O( log1 n ). Proof. Note that v has degree O(log n) whp in Gn/2 , and that Gπ(v) ⊆ Gn/2 . By Lemma 6.1, each shell contains at most O( logn2 n ) vertices. Since the neighbors of v in Gn/2 are distributed uniformly at random among π[n/2, n], we have that each neighbor has a O( log12 n ) chance of appearing in v’s shell, so by a union bound, there is a O( log1 n ) chance of any neighbor appearing in v’s shell. Lemma 6.4. Given a set of ready vertices Q, subselecting the elements X in a particular shell can be done in O(|X|) work and O(log n) depth. Proof. We implement our set of ready vertices Q as an array of O(log3 n) bags, one per shell. Because shells are by permutation value, we can easily determine which bag a vertex belongs in. To extract a particular shell, we output all of the elements in that bag. Note that to store which shells are nonempty, we store O(log2 n) words, each with O(log n) bits. We can thus iterate through T nonempty shells in O(T + log2 n) work and depth using standard table lookup. 23
6.2
Depth
Suppose we are processing shell i. Note that all earlier shells are finalized (their marks do not change), and vertices in shells later than i do not affect the behavior of the queue when processing shell i. We will process all vertices in Q in shell i every round. Consider the set of vertices in the shell Vi , and the set of marked vertices in shell i at the beginning of round r, Mr . Note that a while loop contains two rounds, one round of lowering followed by one round of raising. In this subsection, we use M to denote whether or not a vertex is marked, rather than l(u) = u as in Section 5. For the purposes of this subsection, we count raising and lowering as separate rounds (i.e. two rounds per while loop iteration). We consider round 1 to be the lowering stage of the first while loop iteration: marks and unmarks directly from the batch endpoints occur before the first round. Definition 2. We say that a vertex v finalizes at round i if for all x ≥ i, it holds that v ∈ Mi ⇐⇒ v ∈ Mx , v ∈ / Mi ⇐⇒ v ∈ / Mx (v does not change during round i or any future round), and if v ∈ Mi−1 ∆Mi (v changed during round i − 1). This means that the vertex stops switching between in and out of the marked set. Similarly, we call a set finalized if all vertices in the set are finalized. We say that a vertex finalizes in round 1 if it never changes mark during the while loop. Lemma 6.5. Suppose that v ends marked and finalizes in round r ≥ 4. Then there exists earlier neighbor u that finalizes in round r − 1. Proof. Because v finalizes in round r, and a vertex can only finalize as marked at the beginning of a lowering round, it follows that r − 1 and r − 3 are raising rounds, and that r and r − 2 are lowering rounds. We note that it is either the case that v was marked at the beginning of round r − 2, but unmarked during round r − 2 (Case 1), or that v was unmarked at the beginning of round r − 2 (Case 2), because if neither was the case, then v would have finalized in round r − 2 or earlier. Case 1: v was marked at beginning of round r − 2, but unmarked during round r − 2. Then at the beginning of round r − 2, v had an earlier marked neighbor u. Note that u will end up unmarked (independence property), but finalizes no earlier than round r − 1 because u is marked at the beginning of r − 2. Also note that u finalizes no later than round r − 1 because if u was marked at the beginning of round r − 1, then u would prevent v from marking, pushing back v’s finalization time. Therefore, u’s finalization time is r − 1. Case 2: At the beginning of round r − 2, v was not marked. Therefore, at the beginning of round r − 3, v has an earlier marked neighbor u. Note that u settles by the beginning of round r − 1 so that v may finalize, but no earlier than round r − 1 (as u can only finalize at the beginning of a raising round), therefore u finalizes in round r − 1.
Lemma 6.6. Suppose that v finalizes at the beginning of round r. Then there exists an AE-path of length at least r − 4 (in the new graph) that ends with v. Proof. We prove by induction on the round that v finalizes. Base Case: r ≤ 4: A single vertex is a path of length 0. Inductive step (r > 4): we case on whether v ends marked. 24
Case 1: v ends marked. By Lemma 6.5, there exists an earlier neighbor u with finalization time r − 1. By the IH, there is an AE-path to u of length r − 5, so attaching (u, v) yields an AE-path of length r − 4 as desired. Case 2: v ends unmarked. Note that r is a raising round. Let w be the (final) eliminator of v. If w finalized (at the beginning of) round r − 3 or earlier, then v would have finalized in round r − 2 or earlier, a contradiction. Therefore w finalized in round r − 1 or later. Note that w finalized no later than round r − 1, for v to finalize in round r. Applying the IH yields an AE-path of length r − 5, which attached to (w, v) gives an AE-path of length r − 4.
Lemma 6.7. A single shell takes O(log n) rounds of the while loop to finish whp. Proof of Lemma 6.7. Since the length of all AE-paths is c log n whp for some constant c, whp there does not exist any AE-path of length c log n + 1 or greater, so by Lemma 6.6 no vertex finalizes in rounds c log n + O(1) or later. Therefore, all vertices finalize within the first O(log n) rounds whp. Within a shell, note that all vertices in Q are processed every round. For a vertex to add to the queue, by construction of our propagation algorithm, it must have changed mark. But a finalized vertex cannot change mark. Therefore, after O(log n) rounds, no more vertices are added to the queue, so the shell finishes after O(log n) rounds. Lemma 6.8. The total depth of the algorithm is O(log5 n) whp. Proof. We have O(log3 n) shells, O(log n) rounds per shell, and O(log n) depth for parallel primitives per round, for a total of O(log5 n). Note that our depth bounds are loose upper bounds, for example, some shells will be empty if the batch size is small. Therefore, for b = 1, our work bound (that we will achieve) of O(log2 n log ∆) is smaller than our depth bound of O(log5 n). For clarity we do not attempt to parameterize our depth by b.
6.3
Work
We now will use the shells, and additional techniques, to bound the work of our algorithm. Lemma 6.9. We have the following bounds. n 1. Calling lower j to i costs O(min(∆, n log i )) whp. n 2. Calling raise j from i costs O(min(∆, n log i )) whp. n 3. The number of vertices in N h (i) is bounded by O(min(∆, n log i )) whp. n 2 4. Processing a vertex v in the queue costs O(min(∆2 , ( n log v ) )) work whp.
Proof. In each of these statements, we take the min with ∆, because the cost is proportional to the number of neighbors accessed, which is always bounded by ∆. Note that we can fetch the in-neighbors after time i, in constant time per neighbor after time i by outputting from each bag in the desired range. Even though the earliest bag will contain 25
neighbors earlier than i, we can filter these out efficiently, because the number of filtered neighbors is within a constant factor of the number of total neighbors fetched, because the bags are of doubling elimination time range. 1. Note that all neighbors of j with elimination time from i to j have permutation value at least i, since elimination time is no more than permutation time. Thus, N − (j, i) existed entirely n in the graph snapshot right before time i, which by Lemma 3.1 has O(min(∆, n log i )) max degree whp. 2. The set of neighbors of j with elimination time at least i all have permutation time at least n i, and therefore existed in the graph right before time i. Therefore, O(min(∆, n log i )) is a bound on the number of such vertices. 3. Note that all neighbors in N h (i) have later deletion and permutation time than i, and therefore n existed right before time i, so O(min(∆, n log i )) bounds the number of these. n h 4. When vertex v is processed, up to O( n log v ) neighbors (the size of N (v)) are raised/lowered, n 2 n log n and a raise/lower costs O(min(∆, v )), for total 2-hop cost of O(min(∆2 , ( n log v ) )).
Lemma 6.10. If a vertex v in shell i has no neighbors in shell i, then it is processed (added and removed from queue) at most once by our algorithm. Otherwise, v is processed at most O(log n) times whp. Proof. First suppose that v has no neighbors in the shell. Note that a vertex can only be added to the ready bag by a neighbor being processed. Furthermore, when we are processing a shell, although we may add vertices from later shells, we only will process vertices in the current shell. Therefore, no vertex will add v to the queue while processing shell i, so v can only be processed if it was already in the queue (in which case, will be processed at most once). Now suppose that v does have neighbors in the shell. By Lemma 6.7, we can spend at most O(log n) rounds processing a single shell. At worst, we will process v in each of these rounds. Therefore, v gets processed at most O(log n) times. P Lemma 6.11. Let Si be the influenced vertices in shell i.PProcessing shell i will take O( v∈Si Zv ) expected work. Thus, summing over shells, we have O( v∈S Zv ) expected work within all of the shells. Proof. By the cost bounding lemma on processes, each time we process a vertex v we pay at most O(Zv ). By Lemmas 6.2 and 6.3, a vertex has a O( log1 n ) chance of having any neighbors in its shell. By Lemma 6.10, a vertex with no neighbors will be processed once, and a vertex with neighbors will be processed at most O(log n) times. Thus by linearity of expectation we pay O(Zv ) per vertex in expectation when the dependence depth is shallow. Consider the (very unlikely) event where the dependence depth is not bounded by O(log n). Because within a shell, we process every vertex (in the shell) in every round, the worst possible number of rounds for a shell is 2n. Therefore, our overall bound is this case is polynomial, which is negligible against a whp bound. Therefore, in expectation, we pay O(Zv ) per vertex.
26
Lemma 6.12. Suppose that E1? is the set of batch update edges (of size b), and that V1? is empty. For i < n/4, we have E[Vi? ] ≤ 4bi n . We will prove this lemma by instrumenting InfluenceMIS: instead of adding u to the influence set, we will add Zu to a cost counter. Before proving this lemma, we make two important remarks. 1. If we added 1 to our counter instead of Zv , then we would be counting the size of the influence set. 2. This proof will proceed similarly to that of Lemma 4.3. However, there is a critical difference. The point of Lemma 4.3 was to bound the sum of the undecided vertices and edges, without caring about the distribution between these two sets. In this lemma on the other hand, we are trying to show that given no initially undecided vertices and some undecided edges, the growth of the undecided vertices (transfer from undecided edges to vertices) is slow. Proof of Lemma 6.12. Base Case, i = 1 (before any iteration), true because V1? empty. ? ]. By the IH we have that E[V ? ] ≤ 4bi . We will consider the Inductive step: Consider E[Vi+1 i n effect of decided edges in growing the undecided vertex set, then consider the effect of undecided edges. Suppose that a vertex v ∈ Vi? has dv edges incident to alive vertices not in Vi? right before time i via decided edges. Picking v as the next vertex would add dv vertices to the undecided set (and remove itself), but picking a vertex u where u ̸∈ Vi? and (u, v) ∈ E \ Ei? would remove v from the undecided set. Therefore, the net effect along decided edges is 0. 2 Along undecided edges, at best, we have a n−i+1 chance of selecting the edge, which would add 1 vertex to the undecided set. Note that there are at most b undecided edges. 2b Therefore, the expected undecided vertex set size after time i is upper bounded by 4bi n + n−i+1 ≤ 4b(i+1) . n
P Lemma 6.13. E[ v∈S Zv ] ≤ O(b log2 n log ∆). P Proof. Note that we have two ways of counting Eπ [ v∈S Zv ]. The first is to sum over each vertex that actually enters the influence set. The second is to sum over the batch influence MIS construction, adding the 2-hop neighborhood charge if a vertex is added during that iteration. The latter view helps significantly for bounding the work. We note that in this proof, when we write j, we mean iteration j, we do not mean the vertex at the permutation position j. This is because the vertex at permutation position j is a random choice, which is critical to our bound. Observe that n X X E[ Zv ] = P r[π(j) enters influence set]Zj (3) v∈S
j=1
We will consider separately iterations n/4 through n and iterations 1 through n/4. For iterations n/4 through n, note that there is a O(log vertex, so Zv ≤ O(log2 n) Pn) degree bound whp on each 2 for all v ∈ π[n/4, n] whp. Therefore, E[ v∈S|π(v)≥n/4 Zv ] ≤ O(|S| log n), which by Lemma 4.4 is bounded by O(b log2 n). Now consider iterations 1 through n/4. Each vertex not present in the permutation has an equal chance of being π(j). A vertex will enter the influence set (and pay Zj ) iff it is in the undecided 27
|V ? |
j vertex set Vj? . Therefore, there is a n−j+1 ≤
2|Vj? | n
chance that a vertex joins the influence set P 2|Vj? | 2E[|Vj? |] during iteration j. Thus we have that P r[π(j) enters influence set] ≤ π[1:j) n1 = . n n (j−1) Thus we have that n/4 X
n/4 X 2E[|Vj? |]
P r[π(j) enters influence set]Zj ≤
j=1
n
j=1
Zj .
Now by Lemma 6.12, we have that E[|Vj? |] ≤ 4bj n , so we have that n/4 X 2E[|Vj? |]
n
j=1
Zj ≤
n/4 X 8bj j=1
n2
2
min ∆ ,
n log n j
2 ! .
n 2 n log n Note that ∆2 < ( n log j ) when j < ∆ , and so we split the summation accordingly. Simplifying, we have that n log n ∆
X 8bj j=1
n
min ∆2 , 2
n log n j
n log n ∆
2 ! =
X 8bj n2
j=1
≤
n log n ∆
∆2
2
8b∆2 n2
= O(b log2 n). Using the log approximation of a partial sum, observe that n/4 X j=
8bj min ∆2 , 2 n n log n ∆
n log n j
n/4 X
2 ! =
j=
8bj n2 n log n
n log n j
2
∆
2
= 8b log n
n/4 X j=
1 j n log n ∆
n log n 2 ≤ O b log n log(n/4) − log ∆ = O(b log2 n log ∆). Therefore, the overall bound for the sum until j = n/4 is O(b log2 n log ∆). Thus the overall cost is O(b log2 n log ∆). Theorem 6.14. The total work of our algorithm is expected O(b log2 n log ∆) on a batch of size b. P Proof. By Lemma 6.11, the total cost of our algorithm is O( v∈S Zv ), which by Lemma 6.13 is bound by O(b log2 n log ∆).
28
Note that if we did not use shells, we would significantly improve our depth bound, but at the cost of potentially processing every influenced vertex in every round. This would lead to an O(log2 n) depth bound (whp) and O(b log3 n log ∆) (expected) work bound. Note that the depth would be the same asymptotically as the depth for parallel static R-LFMIS. Corollary 6.14.1. There exists an algorithm for dynamically maintaining an R-LFMIS with expected O(b log3 n log ∆) work on a batch of size b, and O(log2 n) depth whp. On the other hand, making our algorithm fully sequential (processing the vertices one at a time, in priority queue order) would not further improve our work bound. Thus, our parallel algorithm is work-efficient.
7
Conclusion
-In this work, we have given an algorithm for maintaining a maximal independent set that supports batch-dynamic edge updates in O(b log2 n log ∆) expected work and polylog depth whp on a batch of size b. Noting that the expected neighborhood size of the ith vertex is O(n/i) in expectation n (in addition to being O( n log i ) whp), it would be interesting to try to reduce the number of log factors in our work. We note that a recent Masters’ thesis by Krekelberg attempted to develop a O(log2 n) time sequential dynamic algorithm for MIS, but appears to contain unproven technical lemmas and is incomplete [40]. Despite the high-level similarity between dynamic maximal matching and MIS, there is a gap currently between the state of the art dynamic MIS and maximal matching algorithms: the current best sequential dynamic lexicographic-first maximal matching algorithm has O(log log2 n) runtime [21]. Past work has also discussed the gap between these algorithms [9]. Future work could attempt to find better bounds for MIS, or show lower bounds. There has also been work on dynamic MIS on uniformly sparse graphs that relies on maintaining a low out-degree orientation [46]. Noting that parallel batch-dynamic algorithms were recently developed for low out-degree orientation [14], it would be interesting to try to parallelize Onak et al.’s techniques to improve the logarithmic term on uniformly sparse graphs. Acknowledgements. This material is based upon work performed while attending the AlgoPARC Workshop on Parallel Algorithms and Data Structures at the University of Hawaii at Manoa, in part supported by the National Science Foundation under Grant CCF2452276. This work was also supported by NSF grants CCF2403235, CNS231719, CCF2119352, CCF1919223, CCF1918989, and CCF2106759.
References [1] Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. Parallel batchdynamic graph connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 2019. [2] Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel batch-dynamic trees via change propagation. In European Symposium on Algorithms (ESA), 2020.
29
[3] Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Shan Leung Maverick Woo. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, page 531–540, USA, 2004. Society for Industrial and Applied Mathematics. [4] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5), November 2008. [5] Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567–583, 1986. [6] Daniel Anderson and Guy E. Blelloch. Parallel minimum cuts in O(m log2 n) work and low depth. ACM Transactions on Parallel Computing (TOPC), 10(4):18:1–18:28, 2023. [7] Daniel Anderson and Guy E. Blelloch. Deterministic and low-span work-efficient parallel batchdynamic trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 247–258. ACM, 2024. [8] Daniel Anderson, Guy E. Blelloch, and Kanat Tangwongsan. Work-efficient batch-incremental minimum spanning trees with applications to the sliding-window model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020. [9] Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 815–826, New York, NY, USA, 2018. Association for Computing Machinery. [10] Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear in n update time. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019. [11] MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023. [12] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 382–405, 2019. [13] Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, and Thatchaphol Saranurak. Separations between oblivious and adaptive adversaries for natural dynamic graph problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2026. [14] Guy Blelloch, Andrew Brady, Laxman Dhulipala, Jeremy Fineman, Kishen Gowda, and Chase Hutton. Faster parallel batch-dynamic algorithms for low out-degree orientation. CoRR, abs/2602.17811v1. [15] Guy E. Blelloch and Andrew C. Brady. Parallel batch-dynamic maximal matching with constant work per update. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025. 30
[16] Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. Optimal parallel algorithms in the binary-forking model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020. [17] Guy E. Blelloch, Jeremy T Fineman, and Julian Shun. Greedy sequential maximal independent set and matching are parallel on average. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2012. [18] Keren Censor-Hillel, Elad Haramaty, and Zohar Karnin. Optimal dynamic distributed MIS. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16, page 217–226, New York, NY, USA, 2016. Association for Computing Machinery. [19] Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 370–381, 2019. [20] Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Inf. Control, 64, March 1985. [21] Rathish Das and William Kuszmaul. History-independent maximal matchings can be surprisingly efficient, and lead to better worst-case guarantees. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2026. [22] Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin Newport. Leader election in shared spectrum radio networks. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC ’12, page 215–224, New York, NY, USA, 2012. Association for Computing Machinery. [23] Quinten De Man, Laxman Dhulipala, Adam Karczmarz, Jakub Lacki, Julian Shun, and Zhongqi Wang. Towards scalable and practical batch-dynamic connectivity. Proc. VLDB Endow., 18(3):889–901, November 2024. [24] Quinten De Man, Atharva Sharma, Kishen N Gowda, and Laxman Dhulipala. Ufo trees: Practical and provably-efficient parallel batch-dynamic trees. In Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP ’26, page 109–122, New York, NY, USA, 2026. Association for Computing Machinery. [25] Laxman Dhulipala, Quanquan C Liu, Julian Shun, and Shangdi Yu. Parallel batch-dynamic k-clique counting. In ACM-SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), 2021. [26] Yuhao Du and Hengjie Zhang. Improved Algorithms for Fully Dynamic Maximal Independent Set. CoRR, abs/1804.08908, 2018. [27] Manuela Fischer and Andreas Noever. Tight analysis of parallel randomized greedy MIS. ACM Transactions on Algorithms (TALG), 16(1), December 2019. [28] Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2148–2179, 2024. 31
[29] Mohsen Ghaffari, Christoph Grunau, and Jiahao Qu. Nearly work-efficient parallel DFS in undirected graphs. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 273–283, New York, NY, USA, 2023. Association for Computing Machinery. [30] Mohsen Ghaffari and Jaehyun Koo. Dynamic graph coloring: Sequential, parallel, and distributed. CoRR, abs/2512.09218, 2025. [31] Mohsen Ghaffari and Jaehyun Koo. Parallel batch-dynamic algorithms for spanners, and extensions. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 299–313, New York, NY, USA, 2025. Association for Computing Machinery. [32] Mohsen Ghaffari and Jaehyun Koo. Parallel batch-dynamic coreness decomposition with worstcase guarantees. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 225–239, New York, NY, USA, 2025. Association for Computing Machinery. [33] Mohsen Ghaffari and Anton Trygub. Parallel dynamic maximal matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024. [34] Yan Gu, Julian Shun, Yihan Sun, and Guy E Blelloch. A top-down parallel semisort. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015. [35] Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for Maximal Independent Set, Maximum Flow and Maximum Matching, pages 86–91. [36] Chase Hutton and Adam Melrod. Parallel batch-dynamic vertex coloring in O(log ∆) amortized update time. CoRR, abs/2512.08742, 2025. [37] Humza Ikram, Andrew C. Brady, Daniel Anderson, and Guy E. Blelloch. Parallel batch queries on dynamic trees: Algorithms and experiments. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025. [38] Joseph JáJá. An Introduction to Parallel Algorithms. Addison Wesley Longman Publishing Co., Inc., USA, 1992. [39] Richard M. Karp and Avi Wigderson. A fast parallel algorithm for the maximal independent set problem. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC ’84, page 266–272, New York, NY, USA, 1984. Association for Computing Machinery. [40] Bob Krekelberg. Fully dynamic maximall independent set in polylogarithmic update time. Master’s thesis, Eindhoven University of Technology, 2023. [41] Nathan Linial. Distributive graph algorithms global solutions from local data. In 28th Annual Symposium on Foundations of Computer Science, pages 331–335, 1987. [42] Quanquan C Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun. Parallel batchdynamic algorithms for k-core decomposition and related graph problems. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 191–204, 2022. 32
[43] Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. on Computing, 15, 1986. [44] Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’08, page 327–336, USA, 2008. IEEE Computer Society. [45] Prajjwal Nijhara, Aditya Trivedi, and Dip Sankar Banerjee. Fast maximal independent sets on dynamic graphs. In 2025 33rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 78–85, 2025. [46] Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic MIS in uniformly sparse graphs. ACM Transactions on Algorithms (TALG), 16(2):1–19, 2020. [47] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. [48] Natcha Simsiri, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Work-efficient parallel union-find with applications to incremental graph connectivity. In European Conference on Parallel Processing (Euro-Par), 2016. [49] Aditya Trivedi, Prajjwal Nijhara, and Dip Sankar Banerjee. Fast mis on incremental graphs. In 2024 IEEE 31st International Conference on High Performance Computing, Data and Analytics Workshop (HiPCW), pages 139–140, 2024. [50] Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. Batch-parallel Euler tour trees. Algorithm Engineering and Experiments (ALENEX), 2019. [51] Tom Tseng, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’22, page 233–245, New York, NY, USA, 2022. Association for Computing Machinery. [52] Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, and Tjin de Vos. Parallel minimum cost flow in near-linear work and square root depth for dense instances. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 1–16, New York, NY, USA, 2025. Association for Computing Machinery.
33
8
Appendix
8.1
Batch processing operations
In our algorithms, we often will apply a map and filter to a list of pairs, as shown below. Let L be an array, where each element is a pair (u, n), for some variable u and value n. In the function setMins, we want to set a field of u, l(u), to be the minimum of the given pairs. If u is not present in a pair, then we want to leave l(u) unchanged. A first attempt at such a function would look like the following. setMinsUnsafe(L): parfor (u, n) ∈ L: l(u) ← min(l(u), n)
However, because concurrent writes have an arbitrary output, and this involves concurrent writes, we need an alternative. Note that we can do the same effect in a concurrency-safe manner by using a groupBy (which is implemented with a semisort), as follows. setMinsSafe(L): L′ ← groupBy(L) parfor (v, N ) ∈ L′ : l(v) ← min(N )
This has the same expected work and (whp) span as above (in binary forking), but is concurrencysafe. However, in pseudocode this is more complicated, and confuses reading. Thus, in this work, we will write pseudocode in the first form, with the understanding that to avoid concurrency issues an actual implementation would look more like the second form. We note that prior work in the field does the same [15].
8.2
Challenge: Transferring Runtime Arguments of Prior Work
First, note that the batch influence set is not the union of the individual edge update influence sets, and so the work of the batch algorithm is not bounded by the sum of the work of the sequential updates. However, not even the proof approaches of CZ and BDHSS for bounding the runtime transfer to the batch setting. We will discuss in detail the issue of bounding the 2-level neighborhood of influence set vertices. When a vertex early in the permutation is in the influence set, its surviving 2-level neighborhood size is large, and processing this vertex is more expensive than processing a vertex late in the permutation. This neighborhood size is partially bounded in CZ and BDHSS by the time of the later endpoint of the dynamic edge update. Consider a set of updates (ui , vi ), where ui < vi , and v1 = argmini vi . Although we could process O(1) vertices at time v1 , processing all O(b) vertices expected to be in the batch influence set at time v1 would be too costly. It is technically difficult to assign responsibility for influenced vertices to the edge that directly influenced them (or influenced via some path) because some vertices are influenced by more than one edge and since the influence set itself is randomly selected by the same randomness that is giving the vertices their relative positions in the permutation.
8.3
Verifying an LFMIS
Lemma 8.1. We have that a set M is the LFMIS on π iff the following two conditions hold: 34
1. for all u ̸∈ M , there exists v ∈ N (u) ∩ M with π(v) < π(u) (all unmarked vertices have an earlier marked neighbor). This encapsualtes maximality and the lexicographic first condition. Note that N (u) means the neighbors of u. 2. M is independent (for all u, v ∈ M , (u, v) ̸∈ E) Proof. For the forward direction of the implication, suppose that M is the LFMIS. Then all unmarked vertices have an earlier marked neighbor (an eliminator). Furthermore, no two adjacent vertices are marked. Now for the backward direction of the implication, suppose that for all u ̸∈ M , there exists v ∈ N (u) ∩ M with π(v) < π(u), and that for all u, v ∈ M , that (u, v) ̸∈ E. We perform induction on the loop of the LFMIS construction. Base case: the first vertex. Note that u = π(1) ∈ LFMIS. Suppose BWOC that u ̸∈ M . Then there exists an earlier marked neighbor of 1, but there are no earlier neighbors of 1 at all, resulting in a contradiction. Therefore u ∈ M . Inductive step: suppose that the LFMIS and M agree on vertices with π values 1 through r − 1, consider vr = π(r). Case 1: vr is not in the LFMIS. Suppose BWOC that vr is in M . By construction of the LFMIS, note that there exists an earlier neighbor v in the LFMIS. By the IH, M and the LFMIS agree on v, so v ∈ M . But v and vr being adjacent and both marked this contradicts the condition that M is independent, thus vr ∈ M . Case 2: vr is in the LFMIS. Suppose BWOC that vr not in M . Then by our requirement we have an earlier neighbor v ∈ M . By the IH, v would be in the LFMIS, but then v would have eliminated vr , which is a contradiction. Thus vr ∈ M . Therefore the LFMIS and M agree.
35