arXiv CSopen access

Fully Dynamic Rooted Spanning Tree on GPU

Fully Dynamic Rooted Spanning Tree on GPU Abhijeet Sahu, Harmit Singh, Soham Nandy, G. Ramakrishna

arXiv:2607.20211v1 [cs.DC] 22 Jul 2026

Indian Institute of Technology Tirupati, India, 517619 {cs22s501, cs20b012, cs20b046, rama}@iittp.ac.in

Abstract—Spanning trees are fundamental structures in graph theory, essential for various applications such as network maintenance, routing adjustments, and many more. The dynamic nature of real-world networks requires efficient updates to these structures as the underlying graph evolves. Maintaining rooted spanning trees dynamically is particularly crucial for algorithms addressing 2-connected components and minimumweighted spanning trees. In this paper, we address the challenge of maintaining a rooted spanning forest when a batch of edges are inserted or deleted. We present four novel fully dynamic parallel algorithms to update the spanning forest without reconstructing it from scratch. To the best of our knowledge, parallel algorithms for this problem remain largely unexplored. Our experiments on a diverse collection of real-world graphs using a GPU environment demonstrate a throughput of 2 million insertions and 1.4 million deletions per second, significantly outperforming state-of-the-art parallel static algorithms. Index Terms—Dynamic graph, fully dynamic, batch updates, spanning tree

I. I NTRODUCTION The efficient processing of large graphs is increasingly vital across various computational domains, as recent studies underscore the growing complexity and scale of networks [1]. The rise of online social networks and other dynamic environments demands rapid computations of various graph metrics [2]. Real-world networks, such as those in transportation, biology, and social platforms, experience continuous changes or “churn”. For instance, on a popular social media platform “Reddit”, users frequently join and leave subreddits, leading to constant additions and deletions of connections within the underlying network. These frequent updates pose a significant challenge: efficiently updating vital graph metrics as the graph undergoes changes. Traditional methods of analysing static snapshots of these networks fall short, given the rapid pace of these changes. This problem has created a new demand for the development of algorithms tailored for dynamic graphs, where edges can be frequently inserted or deleted. A common approach is to accumulate updates into batches that can be processed in parallel. This approach improves performance as it reduces redundant computations and increases parallelism, although it introduces its own set of challenges. Spanning trees are fundamental to many graph-related applications, playing a critical role in fields like telecommunications, the Internet of Things, transportation, and more. Many crucial network tasks, such as database maintenance, can be executed efficiently using a tree that spans the network. Maintaining spanning trees efficiently in dynamic networks is more practical and resource-efficient than rebuilding them from scratch

after each update. This approach not only accelerates tree construction, but also significantly improves the performance of dependent dynamic algorithms such as biconnected components (BCC), minimum weight spanning Tree (MST), centrality measures, and others. For example, updating a rooted spanning tree is required as a subroutine in dynamic batch updates of MST [2] and biconnected components BCC [3] algorithms. However, the current MST algorithm resorts to completely rebuilding the tree, even when updates to an existing rooted spanning tree would suffice. In the dynamic BCC algorithms, the dynamic maintenance of a rooted spanning tree is required. While some level of parallelism is achieved by processing multiple broken trees concurrently, but the path reversal within each tree is done serially by a single thread. Although this coarse-grained parallelism suits multicore CPU, it is not ideal for modern GPU s, where fine-grain parallelism is expected. Additionally, the unique memory hierarchy of GPUs, coupled with the irregular data access patterns in graphs, necessitates careful design of data layouts and memory accesses. Thus, designing graph algorithms for GPUs requires meticulous attention to both parallelism and memory management. In this paper, we propose GPU based parallel algorithms to dynamically update a rooted spanning tree or forest following the insertion or deletion of a batch of edges. We now formally define the problem. Dynamic Rooted Spanning Forest (D - RSF) Input: An undirected graph G = (V, E), a rooted spanning forest F of G, a batch B of edges, and an operation op ∈ {insert, delete}. Output: A rooted spanning forest F ′ of the updated graph G′ , where ( G + B if op = insert, ′ G = G − B if op = delete.

Given a graph G with V vertices and E edges, and a rooted spanning forest F of G, and a batch B of edges to be inserted or deleted according to an operation op ∈ {insert, delete} the goal is to efficiently maintain F through these dynamic updates. Specifically, the aim is to update the spanning forest dynamically from the current solution, rather than reconstructing the spanning forest from scratch after each operation.

A. Related Work Over the decades, spanning trees have been widely studied across various computational models, with recent focus shifting towards dynamic spanning trees due to the need for efficient algorithms capable of handling dynamic updates. Static Algorithms. Merrill et al. [4], proposed a work-efficient BFS algorithm using the Prefix Sum technique. While BFSbased methods are efficient for graphs with small diameters, they suffer from performance degradation as the graph depth increases [5]. Beyond BFS, different parallel algorithms for constructing spanning trees have also been explored. Cong et al. [6] proposed a multicore algorithm based on the parallel Union-Find technique, combining grafting and broadcasting to reverse paths and construct a rooted spanning tree. However, the GPU implementation of PR - RST algorithm experiences computational overhead due to multiple rounds of pointer jumping, leading to increased complexity and irregular memory access patterns. A fundamental limitation shared by all static approaches is that they do not exploit the existing spanning forest when the graph is updated. Even for small changes (e.g., 1–2% of edges), a full recomputation over the entire graph is required, making them ill-suited for dynamic settings. Sequential Dynamic Algorithms. To address this issue, Eppstein et al. proposed the Sparsification Technique, a widely recognized paradigm in sequential settings for designing dynamic graph algorithms [7], applicable to connected components, biconnected components, and minimum weight spanning trees. Nevertheless, the sparsification technique has notable limitations, including its inherent sequential nature and its focus on single-edge updates. Although this approach has been successfully adapted for dynamic connected components [8], it proved unsuitable for maintaining minimum weight spanning trees in multicore architectures [2], likely due to associated overheads. Furthermore, empirical studies by Haryan et al. [3] demonstrated that the sparsification technique falls short in practice compared to parallel static algorithms for maintaining biconnected components. The exploration of the applicability of the sparsification paradigm to GPU architectures still remains limited, presenting an open research avenue. Parallel Dynamic Algorithms. To overcome the limitations of sequential dynamic algorithms, parallel batch dynamic algorithms have been explored for maintaining spanning forests under batch updates. An algorithm is referred to as fully dynamic if it handles both edge insertions and deletions, whereas incremental and decremental algorithms support only insertions or deletions, respectively. To the best of our knowledge, three notable contributions on fully dynamic spanning forests are [9]–[11]. The HDT (Holm, de Lichtenberg, and Thorup) algorithm [10] and the cluster forest algorithm [11] provide theoretical guarantees on algorithmic depth, but their practical adaptation to specific architectures such as multi-core processors or GPUs remains unexplored. In particular, adapting these algorithms to

GPU architectures is non-trivial and remains an open research challenge. A key limitation of the HDT algorithm is its requirement to maintain O(log V ) spanning forests within a hierarchical data structure, leading to a space complexity of O(V log V + E). The cluster forest algorithm [11] performs two independent graph traversals in parallel from the endpoints of each deleted edge. While this kind of parallelism is effective on multi-core architectures, it is not well-aligned with the parallel execution model of GPUs due to their architectural constraints. Similarly, the parallel algorithm proposed in [9], though implemented for multi-core systems, lacks theoretical guarantees on depth. This algorithm is based on a static parallel BFS, with its worst-case depth bounded by O(V + E), where V and E denote the number of vertices and edges in the graph. In summary, existing approaches either prioritize theoretical guarantees or focus on architecture-specific optimizations, but not both. In contrast, our work aims to bridge this gap by designing algorithms that offer theoretical guarantees while being well-suited for practical deployment on GPU architectures. A comprehensive comparison of existing works with our proposed approach is presented in Table I.

TABLE I: Depth comparison of algorithms for batch edge operations in dynamic graph algorithms, with SG - ET and HS - ET representing our proposed contributions. Here, V , E, and k, denote the number of vertices, edges, and trees in the underlying forest respectively. Algorithms

Batch-Insert

Batch-Delete

Space

HDT [10] CF [11] SG-ET (ours) HS-ET (ours)

O(log V ) O(log3 V ) O(log V + log2 k) O(log2 V )

O(log3 V ) O(log3 V ) O(log V + log2 k) O(log2 V )

O(V log V + E) O(V + E) O(V + E) O(V + E)

Past work on Dynamic Trees. Dynamic spanning tree problems and dynamic trees are related, but they have different goals. Dynamic trees specifically deal with maintaining a forest of trees, and support insert and delete operations on edges, while ensuring the structure remains acyclic. In contrast, dynamic spanning tree problems operate on general graphs, maintaining a spanning tree while accommodating edge insertions and deletions, making them inherently more complex. The concept of dynamic trees was pioneered by Sleator and Tarjan [12] (1981) with the introduction of link/cut trees for fast network flow applications, later adapted by Frederickson [13] (1983) for dynamic MST updates. Following that, subsequent researchers have expanded this area extensively in both sequential and parallel settings [14], [15]. B. Our Contributions Designing parallel dynamic algorithms for D - RSF, where the algorithm’s depth depends on the number of affected key edges (m) or vertices (n), poses significant challenges. The algorithms presented in this paper directly address these challenges. Our design focuses on achieving low-depth parallel algorithms to ensure practical efficiency, particularly on GPU architectures. To the best of our knowledge, there are no

existing GPU-based parallel algorithms for maintaining rooted spanning forests under dynamic updates. Our key contributions are summarized below: We design and implement four fully dynamic parallel algorithms for the D - RSF problem, specifically tailored for GPU architectures. We formally prove the correctness of our algorithms and demonstrate their practical efficiency in practical large-scale graph settings. • We design a GPU -based parallel subroutine to reverse multiple paths in a rooted spanning forest, and integrate ideas from Hooking-Shortcutting, Broadcasting and Euler-Tour techniques to solve the D - RSF problem. • Our GPU -based parallel algorithms significantly outperform existing state-of-the-art static parallel GPU algorithms, achieving speedups of up to 500× for deletions and up to 900× for insertions. • Beyond maintaining rooted spanning forests, our proposed algorithms can also be applied to maintain the connected components of a graph under dynamic updates, including both edge insertions and deletions.

•

II. G ENERIC A LGORITHM FOR D-RSF In this section, we begin by introducing the necessary notations that are used throughout the description of our D RSF algorithm. We then present an overview of the algorithm, followed by two important subroutines to address the subproblems of oriented replacement edges and path reversal. Finally, we describe the complete generic algorithm using the introduced notation and subroutines. A. Notation Let G = (V (G), E(G)) be an input undirected graph, where V (G) and E(G) denote the set of vertices and edges, respectively in G. A forest F = (V (F ), E(F )) of G is said to be a rooted spanning forest of G if V (F ) = V (G) and for every vertex v in F , there exists a parent except for one vertex in each component. The vertices that do not have parents correspond to root vertices. For an edge e = (x, y) in a rooted tree, where y is the parent of x, we say that the orientation of e is from x to y (x → y).

C. Preliminaries. In this section we begin by discussing key existing algorithms that provide the necessary context for understanding our algorithm. Hooking and Shortcutting (HS) [16]. This is a parallel algorithm inspired by the union-find algorithm for computing connected components and a spanning forest in logarithmic time. This algorithm receives a sequence of edges as input. Conceptually, HS maintains a forest of rooted trees that represent the components identified so far. Each parallel round of the algorithm comprises of two alternating phases, namely Hooking followed by Shortcutting. In the Shortcutting phase, every vertex in a tree “jumps” two levels up its tree (pointer doubling), effectively collapsing paths toward the root and flattening the tree structure. In the hooking step, all the intraedges of rooted trees are discarded. Later, for each edge (u, v) that connects two distinct trees, one tree’s root is made a child of the other, thereby merging components. By careful examination, the formation of cycles is avoided. The edges that were not successfully considered, due to parallelism and race condition will participate in the subsequent rounds. The algorithm alternates between two operations till all the edges are processed successfully. Euler Tour. [5]. For an unrooted tree, a directed graph T ′ can be obtained by replacing each edge (u, v) with two directed edges: (u, v) and (v, u). We define the Euler tour of such an unrooted tree as a path of directed edges in T ′ that visits each edge exactly once and returns to the starting vertex. For an Euler tour on a sequence (e1 , e2 . . . , e2×(n−1) ) of edges, for each 1 ≤ i ≤ 2 × (n − 1), rank of ei is defined as its index i. We use a well-known parallel algorithm technique called the Euler Tour Technique [5] to transform an unrooted tree into a rooted tree, constructing an Euler tour, and computing the ranks of all the edges in of Euler tour.

TABLE II: Notations Notation G V (G), n E E(G) F x→y m k G′ F′ F̂

Description An undirected graph The number of vertices in G The number of edges in G The set of edges in G A rooted spanning forest of G Orientation of an edge from child x to its parent y in F The number of key edges The number of components (trees) in F Graph G after a batch update A rooted spanning forest of G′ F̂ = F − B for deletion operation; F̂ = F for insertion operation

Let F be a rooted spanning forest of G on n vertices. The resultant graph obtained after inserting or deleting a batch B of edges in G is denoted by G′ . We use M to denote a set of potential edges that help to establish the connectivity across the trees in a spanning forest of G′ and such edges are referred as key edges. In case of delete operation, M = E(G) − E(F ) − B, where as M = B for insert operation. We use m to denote the number of key edges. For delete operation, F̂ denote the forest obtained after deleting edges of B from F , whereas F̂ remains same as F for insert operation. Each tree Ti in F̂ is uniquely identified by its root vertex ri . For each vertex v in F̂ , the root vertex of the tree containing v is called as representative, which is denoted by rep[v]. An edge (u, v) ∈ M is a cross edge if rep[u] ̸= rep[v]. Let Ecross be the set of all cross edges in G′ with respect to F̂ . An edge set Er ⊆ Ecross is referred to as replacement edges if |Er | = k − ℓ, and at most one edge from Er appears between any two trees in |F̂ |, where k and ℓ denotes the number of components in F̂ and G′ , respectively.

Key edges

Root vertex

Root vertex

Oriented Replacement Edge

Affected Vertex

7

1

4

a.

6

12 8

9

10

11

3

2

Root vertex

14

13

5

15

16

c.

b.

17

Fig. 1: Overview of the D - RSF algorithm. (a) The black solid lines represent the rooted spanning forest, while the blue edges denote the key edges. (b) Replacement edges are selected from the key edges and oriented appropriately. (c) Parents are updated for affected vertices during path reversal to obtain an updated rooted spanning forest.

B. Overview We now present a high-level overview of our generic parallel algorithm to solve the D - RSF problem. The dynamic algorithm updates the rooted spanning forest of a graph in parallel, based on a batch of edges to be inserted or deleted, without reconstructing it from scratch. First, depending on the type of update operation, we either insert the given batch of edges into the underlying graph or remove them from both the forest and the underlying graph. Next, we identify replacement edges from the available set of key edges to reestablish connectivity across the trees in the forest. Once the replacement edges are identified, assigning their orientations arbitrarily can lead to conflicts where a vertex may end up with multiple parents. For example, in Figure 1(b), both vertices 6 and 17 could attempt to become the parent of vertex 10 if orientations are assigned arbitrarily. Such conflicts can result in the loss of valid orientations for certain edges. Therefore, it is necessary to systematically determine the orientations of the replacement edges before including them in the forest. The task of finding oriented replacement edges constitutes our first subproblem. Although it is possible to assign orientations to replacement edges without causing internal conflicts, these new orientations may still overwrite the parent relationships of existing tree edges. For instance, in Figure 1(b), the addition of a replacement edge (6, 10) could reassign the parent of vertex 6 to vertex 10, thereby causing the loss of the original tree edge (4, 6). To overcome this, we introduce a second subproblem, which involves reversing the directions of a few tree edges to maintain a valid rooted forest. More precisely, we reverse the orientations along certain paths (e.g., the path from vertex 6 to 1 in Figure 1 (b)), and then later insert the replacement edges to obtain the new forest. Overall, the D - RSF problem is divided into two sub-problems. The first sub-problem involves finding the orientated replacement edges across the disconnected trees, while the second aims to reverse the orientations of multiple paths in a forest, shortly called reverse paths.

C. Subroutines To address the two sub-problems proposed earlier, we now present the necessary subroutines. We defer the algorithm details required for these subroutines to later subsections. F IND O RIENTED R EPL E DGES(rep[·], M ): Given the representative array rep[·] for a rooted forest F̂ and a set M of key edges, this subroutine identifies oriented replacement edges from M to establish connectivity across the trees in F̂ . R EVERSE PATHS(R, parent[·])): Given a rooted forest F̂ (represented using the parent[·]) and a set R of pairs, where each pair denotes the end vertices of a path in F̂ . This subroutine reverses the parent-child relationships of all vertices along the paths in R in parallel. Algorithm 1: A GPU Algorithm for Dynamic Rooted Spanning Forest Input: A Graph G = (V, E), a rooted spanning forest F of G represented by parent[·], a batch of edges B, and an operation op ∈ {insert, delete}. Output: A Rooted Spanning Forest F ′ of G′ = G op B 1 M =B 2 if operation is delete then 3 M = (E(G) − E(F )) − B 4 for each edge (u, v) ∈ B in parallel do /* Let v be the parent of u */ 5 parent[u] ← u rep[·] ← parallel pointer jumping on parent[·] E ′ ← F IND O RIENTED R EPL E DGES(M , rep[·]) ′ 8 for each oriented edge (u, v) ∈ E in parallel do /* Let v be the parent of u 9 R = R ∪ {(u, rep[u])} 6 7

F ′ ← R EVERSE PATHS(F̂ , R, parent) ′ 11 Update parent[·] in parallel for each edge in E 12 Insert/Delete B of edges to/from G 10

*/

D. Generic Algorithm An instance of the D - RSF problem involves an undirected graph G, a rooted spanning forest F of G, and a batch B of edges for insertion or deletion. Algorithm 1 begins by identifying the operation type. For deletions, edges in B are removed from the non-tree edges, and the key edges M are computed in parallel (Line 3). Subsequently, for each tree edge in B, the forest F is updated in parallel by setting the parent node to itself (Line 5), effectively deleting all the tree edges in B from the forest. For insert operation, since no nontree edge exists between disconnected trees in the forest, B itself becomes key edges in Line 1. After updating the forest and obtaining key edges, the algorithm proceeds to determine the representative of each vertex, resulting in the rep[·], by applying pointer jumping on the parent array (Line 6). This ensures that each vertex in the forest can retrieve its root vertex quickly in the subsequent tasks. The algorithm then identifies oriented replacement edges E ′ from the set M of key edges using the parallel subroutine F IND O RIENTED R EPL E DGES (Line 7). For instance, As illustrated in Figure 1, it identifies two replacement edges: (6, 10) and (10, 17). However, when including an edge (6, 10) and setting its orientation such that 10 is a parent of 6, it is necessary to reverse the orientations of the edges involved in the path from 6 to 1. Therefore, before incorporating the oriented replacement edges into the forest, we first identify the end vertices of the paths whose orientations must be reversed (Line 9). The paths represented by pairs in R are then reversed using the parallel subroutine R EVERSE PATHS (Line 10). Finally, the new replacement edges are incorporated into the updated forest F ′ (Line 11) using |E ′ | threads, ensuring that the spanning forest remains properly rooted after edge updates. We now present the proof of correctness for the generic algorithm described in Algorithm 1). Theorem 1. Given an undirected graph G, a rooted spanning forest F of G, a batch of edges B to insert or delete, Algorithm 1 produces a valid rooted spanning forest F ′ of G ± B. Proof. Let G′ be the graph and F̂ the forest obtained after the batch updates. Let ℓ denote the number of connected components in G′ and k = |F̂ | represent the number of trees in F̂ . Using the function O RIENTED R EPL E DGES (Line 7), we compute the set of oriented replacement edges Er′ = {e′1 , e′2 , . . . , e′k−ℓ }. Let ek = (x, y) be a replacement edge in Er′ . Consider two trees Ti and Tj ∈ F̂ rooted at ri and rj , respectively, where x ∈ Ti and y ∈ Tj . The simple path from x to the root ri is denoted as P = {x, v1 , v2 , . . . , ri }. After applying R EVERSE PATHS (Line 10), the parent-child relationships along P are reversed, resulting in every vertex v ∈ Ti having a parent, except for x. When the edge (x, y) is inserted, x acquires y as its parent in Line 11. The addition of each replacement edge reduces the number of root vertices in F̂ by one. Starting with k roots, the insertion

of k − ℓ replacement edges decreases the root count to k − (k − ℓ) = ℓ. Therefore, the resulting forest F̂ is a valid rooted spanning forest of G′ with exactly ℓ trees, one per connected component of G′ . III. R EPLACEMENT E DGES AND PATH R EVERSAL The two main subproblems in our generic algorithm to solve D - RSF are finding oriented replacement edges and reversing

multiple independent paths, both in parallel. We propose Supergraph (SG) and Hooking Shortcutting (HS) techniques to address the first problem. Further, we describe Broadcasting (BC) [6] and design Euler Tour (ET) based technique to solve the second. Since there are two distinct approaches to solving two subproblems mentioned, we propose the following four algorithms to solve D - RSF. 1) SG - ET (Supergraph with Euler Tour) 2) SG - BC (Supergraph with Broadcasting) 3) HS - ET (Hooking Shortcutting with Euler Tour) 4) HS - BC (Hooking Shortcutting with Broadcasting) A. Supergraph for Oriented Replacement Edges Given a forest F̂ , a representative array rep[·] to hold representative for every vertex in F̂ and a set M of key edges, we now identify oriented replacement edges. In this supergraph (SG) approach we construct a supergraph G̃ and a hash table using the forest and key edges. The supergraph helps to maintain the topological structure across the trees in the forest, whereas the hash table is useful to retrieve a key edge corresponding to any edge in the supergraph. We first construct a supergraph G̃, in which each vertex corresponds to a tree in the forest F̂ and an edge in the supergraph corresponds to a cross edge across the trees in the forest. In particular, for each root vertex u in F̂ there is a vertex in G̃. We go through all key edges e = (u, v) in parallel and the edge (u, v) is marked as cross edge if rep[u] ̸= rep[v]. We now use a temporary array sedges to capture the potential edges to be added in the supergraph. For each cross edge ei = (u, v) in parallel, we include an edge in G̃ by assigning sedges[i] = (rep[u], rep[v]), and insert a keyvalue pair in a hash table H, where key = (rep[u], rep[v]), and value = (u, v). At this stage, the number of edges in the supergraph equals to the number of cross edges. Multiple cross edges over the same two trees result in duplicate edges in the supergraph. To eliminate such redundant edges, we apply parallel sorting and parallel compaction on sedges. Although multiple pairs with same key attempt to write in the hash table in parallel, eventually no two pairs in the hash table have same key, due to race conditions. In other words, for each edge in the supergraph G̃, we maintain a unique cross edge in the hash table. We now apply PR - RST algorithm [6] on the super graph G̃ to obtain a rooted spanning forest F̃ of G̃. By treating the edges of F̃ as keys, we can retrieve the corresponding cross edges from the hash table and these cross edges become oriented replacement edges. For each edge oriented (u′ , v ′ ) in

F̃ , where u′ is the parent of v ′ , we retrieve a oriented cross edge (u, v) from the hash table H, where u is par[v]. Lemma 1. Given a forest F̂ with k trees and m key edges, oriented replacement edges can be obtained using the supergraph approach in O(log m+log2 k) depth and O(m+k log k) work in the worst case. The merit of this approach is that the depth of this algorithm is independent on the number of vertices n, and only depends on the number of disconnected components and the key edges. However, m can be large in the case of deletion operation, and thus we aim to design a parallel algorithm that minimises the dependency on m in the next subsection. B. Hooking and Shortcutting for Oriented Replacement Edges Algorithm 2: Oriented Replacement Edges using Hooking and Shortcutting Input: key edges M [·], and representative array rep[·] Output: At most k − 1 oriented replacement edges 1 replEdges ← H OOKING -S HORTCUTTING (M, rep) 2 for each ei = (u, v) ∈ replEdges in parallel do 3 sf Edges[i] = (rep[u], rep[v]) 4 H.insert(⟨rep[u], rep[v]⟩, ⟨u, v⟩) 5 6

O ← E ULERIAN -T OUR(sf Edges) R ← H.retrieve(O)

Given the set of key edges M [·] and the representative array rep[·] for a rooted forest F̂ , our method proceeds in two phases. In Phase 1 (Line 1), we apply the H OOKING S HORTCUTTING (HS) procedure to identify at most k − 1 replacement edges that can reconnect the disconnected components. In the HS algorithm presented in [16], each vertex begins as a singleton tree, whereas in our adaptation we begin with an existing forest of partial components. We then apply the same HS steps to efficiently identify replacement edges. In Phase 2 (Line 2 - Line 6), we orient the selected replacement edges. To maintain the topological structure across the trees, we first construct an auxiliary forest by storing, for each replacement edge (u, v), a key-value mapping in a hash table H, where the key is ⟨rep[u], rep[v]⟩ and the value is ⟨u, v⟩ (Line 2). This auxiliary forest, formed by the keys in H, represents a super-forest over the component representatives. We then apply the Eulerian Tour algorithm to this super-forest (Line 5) to obtain a rooted structure. Finally, we retrieve the corresponding original edges from the hash table H (Line 6) to generate the final set of oriented replacement edges. For hash table implementation, we adapted an existing open-source code available online 1 , and modified it to suit our use case. Lemma 2. Algorithm 2 identifies oriented replacement edges in a graph using Hooking and Shortcutting operations in O(log2 n) depth and O((m + n) log n) work. 1 https://nosferalatu.com/SimpleGPUHashTable.html

A key merit of this approach is that its depth depends solely on the number of vertices, not the number of edges. While the HS technique is primarily used to identify oriented replacement edges, it serves as a parallel static algorithm for obtaining a rooted spanning tree. C. Broadcasting Based Path Reversal The purpose of this subroutine is to reverse the orientation of all disjoint paths of a forest, which are specified by R, where each path is represented by a pair (ui , ri ). We use the broadcasting method by Cong et al. [6] to efficiently reverse multiple paths in a forest in parallel. The algorithm begins by identifying all the on-path vertices that lie on the path from ui to ri for each pair in R simultaneously. Once these vertices are identified, the algorithm reverses their parent-child relationships in parallel i.e., if u = parent[v], we now set parent[u] = v. For each vertex u in the tree, an array of size O(log n), referred to as the special ancestor, is maintained. This array stores all ancestors of u at distances equal to powers of 2, using the pointer jumping process. In the subsequent log n iterations, all vertices that lie on the path from ui to ri can be identified in parallel using special ancestors. For further details, we refer to [6]. Lemma 3. (Lemma 1 and 2 from [6]) Given a spanning forest F̂ and a set R of pairs, where each pair represents the end vertices of a disjoint path in F̂ , the paths represented by R can be reversed using the broadcasting technique in O(log n) depth and O(n log n) work. The primary drawback of this technique is its O(n log n) space complexity. Additionally, it faces significant limitations when implemented on a GPU. The multi-step pointer jumping required to construct the special ancestor array involves multiple iterations and external synchronization, resulting in considerable runtime overhead. To overcome these inefficiencies, we propose a linear-space method in the next section that is also tailored for the GPU architecture. D. Eulerian Tour Based Path Reversal Given a rooted forest F̂ and a set R of pairs representing the end vertices of paths in F̂ whose orientation needs to be reversed, we design Algorithm 3 to achieve this using Euler Tour. In F̂ , let f irstEdge[v] and lastEdge[v] denote the first and last edges incident on each vertex v. Each tree in F̂ has its own Eulerian tour, where each tree edge appears twice. As shown in Line 1 of Algorithm 3, we first compute the Euler tours for all trees in F̂ and assign ranks to the edges using the parallel algorithm by Polák et al. [5]. Based on these ranks, we assign start and finish times to each vertex, categorizing them into three groups as outlined in Lines 2–10. The assigned start and finish times for all vertices are shown in Figure 2. For each path (xi , ri ), we update support[ri ] with xi (Line 12), enabling constant-time retrieval in subsequent steps.

In the last for loop of Algorithm 3, we go through all edges and identify the affected edges in Line 15, and reverse their orientations. Each vertex u knows its representative rep[u] (the tree to which it belongs). Using this information, u can easily determine the end vertex of the path (remember support was updated earlier (Line 12)). Thus, v can efficiently verify whether it lies on the path.

IV. C ORRECTNESS AND C OMPLEXITY A NALYSIS In this section, we analyze the depth and work complexity of the four proposed algorithms. We then separately analyze the depth complexity for the insertion and deletion operations. Theorem 3. The SG - BC and SG - ET algorithms insert a batch B of edges in O(log n + log2 k) depth, while the HS - BC and 2 HS - ET algorithms require a depth of O(log n). The total work performed by all algorithms is O(n log n).

Root vertex 0 8 7

0 8 7

0 1 10

1 2 8

2 4 6

7

0 1 10 1 9 3

4 10 6

2 11 2

5 12 5

9 3 9

5 7

1 2 8

2 4 6

3

6

5

3

6

4

74

4

74

7

1 9 3

4 10 6

2 11 2

5 12 5

9 3 9

5 7

5

Fig. 2: Orientation of affected edges, show in solid thick, is reversed. Numbers shown on left and right sides of each vertex correspond to start and finish times, obtained using Euler-Tour.

Algorithm 3: R EVERSE PATHS E ULERT OUR Input: A rooted spanning forest F̂ , set of vertex pairs R, rep[·] and parent[·] arrays Output: Updated parent[·] in the Forest F̂ 1 rank[·] ← E ULERIAN T OUR (parent) 2 for each vertex v in parallel do 3 if v is a Leaf Vertex then 4 start[v] = f inish[v] = rank[⟨v, parent[v]⟩] 5 6 7 8 9 10 11 12

else if v is a Root Vertex then start[v] = rank[f irstEdge[v]] f inish[v] = rank[lastEdge[v]] + 1 else if v is an Intermediate Vertex then start[v] = rank[f irstEdge[v]] f inish[v] = rank[⟨v, parent[v]⟩] for each vertex pairs (xi , ri ) ∈ R in parallel do support[ri ] = xi

for each edge (u, parent[u]) in F̂ in parallel do r = rep[u], x = support[r] 15 if (start[r] < start[u] ≤ start[x]) and (f inish[r] > f inish[u] ≥ f inish[x]) then 16 v = parent[u] 17 parent[v] = u

13

14

Theorem 2. Given a spanning forest F̂ and a set R of pairs, where each pair represents the end vertices of a disjoint path in F̂ , Algorithm 3 reverses the paths represented by R in O(log n) depth and O(n) work.

Theorem 4. The SG - BC and SG - ET algorithms delete a batch B of edge in O(log n+log2 k) depth, while the HS - BC and HS 2 ET algorithms require a depth of O(log n). Both algorithms perform total work of O(E + n log n), where n denotes the number of vertices and E denotes the number of edges in G. The space complexity of the Algorithm 1 is bounded by O(V + E), where V represents the number of vertices and E the number of edges in the graph. This complexity arises from storing the graph (using an edge list) and auxiliary structures such as the parent array, representative (rep) array, and similar data structures. Temporary storage for operations such as compaction, sorting or hash table also scales with V or E. Additionally, O(B) space is required for handling a batch B of edges. Further, broadcasting approach requires O(V log V ) space as each vertex stores upto log V ancestors [6]. Consequently, the SG - BC and HS - BC algorithms consume O(V log V + E) space, whereas SG - ET and HS - ET algorithms consume O(V + E) space. We now proceed to prove the correctness of Algorithm 1 and Algorithm 3. Lemma 4. Let R be a set containing k pairs of vertices (x1 , y1 ), (x2 , y2 ), . . . , (xk , yk ) in a forest F = {T1 , T2 , . . . , Tk }, where yi is the root of a tree Ti ∈ F and xi is a vertex in Ti . Using the start and end times obtained from the Eulerian tour, Algorithm 3 correctly reverses all paths from each xi to its corresponding root yi . Proof. Consider a tree Ti and vertex pair (xi , yi ). Let U to be the set of vertices ui such that f irst[xi ] < f irst[ui ] ≤ f irst[yi ] and V to be the set of vertices vi such that last[xi ] > last[vi ] ≥ last[yi ]. Then P ath(xi , yi ) = {wi | wi ∈ U ∩ V } consists of all vertices in the simple path from xi to yi . ∀ i, j ∈ [1, k] such that i ̸= j, since any two trees Ti , Tj are disjoint, it follows that P ath(xi , yi )∩P ath(xj , yj ) = ∅. Thus, all paths can be reversed without conflicts.

V. E XPERIMENTS AND R ESULTS In this section, we introduce the datasets and the configuration of the experimental platform. We then analyse the performance and scalability of the proposed algorithms compared to the static BFS and PR - RST algorithms. Finally, we highlight key insights and the influencing factors of the RSF algorithm.

TABLE III: Statistics of graphs used in the experiments

A. Experimental Setup and Dataset

B. Comparison with Static Parallel Algorithms In this section, we compare the performance of our proposed algorithms against two static approaches: the parallel BFS algorithm, which is a well-known and commonly used baseline for graph traversal, and the multi-core PR - RST algorithm proposed by Cong et al. [6]. Comparison with Parallel BFS. Parallel BFS algorithms typically assume that the graph is connected; however, when it is not, BFS must be initiated separately for each disconnected component, leading to multiple sequential executions. To eliminate such serial processing, we first add or delete the necessary batch of edges and then identify all disconnected com2 https://github.com/Abhijeetkumar96/batch-dynamic-spanning-tree.git

Dataset

V E Social Networks higgs-twitter 456K 14.8M hollywood-2009 1.1M 56.3M com-Orkut 3.07M 117M soc-LiveJournal1 4.8M 68M Web Graphs uk-2002 18.5M 298M arabic-2005 22.7M 639M uk-2005 39.4M 936M Road Networks Road-USA 23.9M 58M europe osm 50.9M 54.1M Kronecker (Synthetic) Graphs kron g500-logn18 262.1K 10.6M kron g500-logn19 524K 22M 1.0M 45M kron g500-logn20 kron g500-logn21 2.1M 91M 1000

SpeedUp

Abv. TW HW CO LJ UK-02 AR UK-05 RU EO KR-18 KR-19 KR-20 KR-21

SG PR SG ET HS PR HS ET

100

10

CO

TW

AR

RU

LJ

EO

H W U K02 U K05

1

KR -2 1 KR -2 0 KR -1 9 KR -1 8

We conduct our experiments on an NVIDIA A100 GPU with 80 GB of on-board memory, based on the Ampere architecture. The GPU features 6912 CUDA cores, 80 Streaming Multiprocessors (SMs), 2.04 TB/s memory bandwidth, 6 MB of L2 cache, and 128 KB of L1 cache per SM. The GPU is connected to an AMD EPYC 7742 CPU with 64 cores, 4 MB of L1 cache, 32 MB of L2 cache, and 256 MB of L3 cache. The number of threads per block was set to 1024 for all experiments. To facilitate reproducibility and future comparisons, we have made the complete source code used for the experiments, along with all implementation details publicly available.2 To test the capability of our algorithms under dynamic graph updates, we used 13 datasets that include both realworld and synthetic graphs, as listed in Table III. Sourced from various publicly available repositories, these datasets represent road networks, web graphs, co-purchasing networks, and social networks [17], [18], and range from 1 million to 1 billion edges. They are commonly used in evaluations of GPUbased graph algorithms [3], [5], [16]. Prior to our experiments, we preprocessed each graph by treating directed edges as undirected and removing multiple edges and self-loops, similar to other works. Finally, to test the scalability of our algorithms, we check their ability to handle different batch update sizes. We use a wide range of batch update sizes, ranging from 100 to 100,000 edges. The batch edges are selected uniformly at random from the graph. A delete batch created uniformly at random, likely to have fewer tree edges compared to non-tree edges, and thus we choose (approximately 30 - 40%) of the edges from tree edges and the rest from the non-tree edges for a delete batch. For each graph and each batch size, we generate five independent instances. Each instance is executed five times independently, totaling 25 individual executions. The speedup is computed by averaging the ratios of baseline execution time to our method’s execution time over these 25 runs. While multiple batch sizes were evaluated to analyze performance trends, we report results primarily for batch size 10,000 for brevity.

Datasets

Fig. 3: Speedup: Our algorithms w.r.t static GPU BFS for insert

ponents using the method described in [16]. We subsequently use stream compaction to select all unique representatives and apply parallel BFS starting from these representatives. Our results show a maximum speedup of 530× for edge deletion (with an average speedup of 160×) and 900× for edge insertion (with an average speedup of 200×), as illustrated in Figures 3 and 4. The observed improvements in running times can be attributed to the dynamic setting. The size of the largest connected component and the depth of the tree continually change as new batches of edges are inserted or deleted. This variability affects the performance of BFS due to its dependence on the graph’s diameter [5]. However, all of our proposed algorithms, being independent of the tree’s depth, demonstrated significant speedup compared to the baseline, making them more suitable for real-world dynamic graphs. Comparison with PR - RST. PR - RST is a parallel algorithm proposed by by Cong et al. [6] for multi-core CPUs. While BFS has been extensively studied and widely implemented, the multi-core PR - RST algorithm has not yet seen widespread adoption particularly on GPUs, to the best of our knowledge. To enable a fair comparison, we ported the original multi-core implementation to the GPU ourselves. As shown in Figure 5, our best-performing algorithm achieves, on average, a 13× speedup over PR - RST for deletions

SpeedUp

1000

SG PR SG ET HS PR HS ET

100

10

CO

AR

LJ TW

RU

EO K05 U

H W K02 U

KR -2 1 KR -2 0 KR -1 9 KR -1 8

1

Datasets

Fig. 4: Speedup: Our algorithms w.r.t static GPU BFS for delete

(maximum 30×) and an 18× speedup for insertions (maximum 41×). This performance gap is largely due to the fact that PR - RST is a static algorithm that recomputes the entire rooted spanning forest after every update, without leveraging prior computations. Additionally, the construction of the ancestor array (Section III-C) results in numerous uncoalesced memory accesses, which further degrade GPU performance. C. Scalability Analysis: Impact of Increasing Batch Sizes on Performance After evaluating the speedups of our proposed algorithms, we now focus on studying their scalability. Specifically, our goal is to understand how the performance of the algorithms changes with increasing batch sizes. We conducted experiments using batch sizes of 100, 1000, 10,000, and 100,000 edges on the largest graph of each category of datasets in Table III and running times are reported in Figure 5. The results demonstrate that our algorithms maintain strong scalability, with minimal variation in running times across different batch sizes, achieving an average throughput of 2M insertions and 1.4M deletions per second across all batch sizes respectively. This suggests that our algorithms can efficiently handle larger batches without significant performance degradation. D. Influencing Factors in proposed algorithms In this section, we analyze the factors influencing the performance of our algorithms. While all algorithms demonstrated significant speedups and scalability, running times varied across different batches and operations. We now identify the key factors that contribute to these variations. Although deletions theoretically introduce an O(log E) overhead, our experiments reveal that this accounts for only 10-15% of the total runtime. This is largely because the compaction algorithm is highly optimized for GPUs due to its effective parallelization techniques. However, most of the time (approximately 50%) was spent on identifying oriented replacement edges, while path reversal accounted for around 30%, except for insertions in SG-based algorithms. Interestingly, despite both broadcasting and the Eulerian Tour having the same O(log n) complexity for P ath Reversal, the latter

demonstrated superior practical performance. We now explore the rationale behind these observed behaviors. Hooking-Shortcutting vs SuperGraph. For deletions (Figures 6a, 6b), HS runtime scales with the number of vertices n, while SG scales with the number of key edges m. Consequently, HS outperforms SG when n < m, and vice versa. This distinction becomes critical for dense graphs, where m can reach O(n2 ), making SG increasingly inefficient while HS maintains stable performance. For insertions (Figure 6c), SG runtime remains nearly constant since the number of key edges equals the fixed batch size, whereas HS runtime continues to vary with n. As a result, SG consistently outperforms HS for insertions, even on dense graphs, since only the inserted batch is processed. In summary, HS is preferable when n ≪ m, while SG is preferable when m ≪ n. Regarding path reversal, we notice that the Eulerian Tour technique outperforms Broadcasting by a factor of 2 − 3×. This performance gap is primarily due to uncoalesced memory accesses in Broadcasting and number the space complexity involved. In particular, Eulerian Tour technique requires O(n) space, where as Broadcasting requires O(n log n). VI. C ONCLUSION We presented four algorithms for the fully dynamic update of rooted spanning trees in a many-core (GPU) environment. Our algorithms focus on repairing the spanning tree rather than reconstructing it from scratch, using key techniques such as hooking and shortcutting, supergraph-based methods for identifying oriented replacement edges, and Eulerian tour technique for path reversal. Our results demonstrate that incremental tree maintenance is a highly effective strategy for processing massive, evolving graphs on modern accelerators. VII. F UTURE W ORK Several promising directions for future research remain. First, we plan to extend our algorithm to support fully dynamic connectivity beyond spanning trees. Second, we aim to optimize the dynamic updates of auxiliary data structures, such as Euler Tour Trees, to enable more efficient batchparallel queries. Finally, we intend to explore multi-GPU implementations to further scale performance for massive, evolving real-world graphs. ACKNOWLEDGMENT The authors would like to thank the anonymous reviewers for their insightful feedback. We also thank Dr. Dip Sankar Banerjee (IITJ) for providing access to the DGX system support used in this work. R EFERENCES [1] S. Sakr, A. Bonifati, H. Voigt, A. Iosup, K. Ammar, R. Angles, W. Aref, M. Arenas, M. Besta, P. A. Boncz et al., “The future is big graphs: a community view on graph processing systems,” Communications of the ACM, vol. 64, no. 9, pp. 62–71, 2021. [2] S. Srinivasan, S. D. Pollard, B. Norris, S. K. Das, and S. Bhowmick, “A shared-memory algorithm for updating tree-based properties of large dynamic networks,” IEEE Transactions on Big Data, vol. 8, no. 2, pp. 302–317, 2018.

10 5

10 4

10 5

10 3

10 4

10 2

10 5

10 4

10 3

10 2

10 5

10 3

KR-21

2048 512 128 32 8 10 2

10 2

10 5

10 4

10 3

10 2

8

KR-21

2048 512 128 32 8

10 5

16

10 4

32

SG BC

RU

1024 512 256 128 64 10 2

2048 1024 512 256 128 64 10 3

64

(a) Deletion Batch Size

UK-05

HS BC

RU

1024 512 256 128 64

10 5

CO

10 3

10 2

10 5

10 4

10 3

10 2

Runtime [in ms]

32

SG ET

UK-05

2048 1024 512 256 128

10 4

CO

64

HS ET

10 3

PR-RST

10 4

BFS

(b) Insertion Batch Size

0

Datasets

(a) Vertices vs. key edges for deletion (batch size: 10,000).

SG

100 50 0

60

HS

SG

40 20 0

TW KR -19 LW KR -20 HW KR -21 CO UK -02 AR UK -05 RU EO

200M

HS

Running Time (in ms)

400M

150

KR -19 LW KR -20 HW KR -21 CO UK -02 AR UK -05 RU EO

600M

Datasets

Datasets

TW

Key Edges

Running Time [ms]

Nodes

Number of Key Edges

50M 40M 30M 20M 10M 0

TW KR -19 LW KR -20 HW KR -21 CO UK -02 AR UK -05 RU EO

Number of Nodes

Fig. 5: Runtime comparison of baseline and proposed algorithms across various batches for (a) Deletion operation and (b) Insertion operation.

(b) Running times for deletion operations.

(c) Running times for insertion operations.

Fig. 6: HS performance depends on the number of nodes (n), whereas SG performance depends on the number of key edges (m). For insertion, the number of key edges equals the batch size, which is fixed across datasets.

[3] C. A. Haryan, G. Ramakrishna, K. Kothapalli, and D. S. Banerjee, “Shared-memory parallel algorithms for fully dynamic maintenance of 2-connected components,” in International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2022, pp. 1195–1205. [4] D. Merrill, M. Garland, and A. Grimshaw, “Scalable gpu graph traversal,” ACM Sigplan Notices, vol. 47, no. 8, pp. 117–128, 2012. [5] A. Polak, A. Siwiec, and M. Stobierski, “Euler meets gpu: practical graph algorithms with theoretical guarantees,” in 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2021, pp. 233–244. [6] G. Cong and D. A. Bader, “The euler tour technique and parallel rooted spanning tree,” in International Conference on Parallel Processing, 2004. ICPP 2004. IEEE, 2004, pp. 448–457. [7] D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig, “Sparsification—a technique for speeding up dynamic graph algorithms,” Journal of the ACM (JACM), vol. 44, no. 5, pp. 669–696, 1997. [8] S. Srinivasan, S. Bhowmick, and S. Das, “Application of graph sparsification in developing parallel algorithms for updating connected components,” in 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 2016, pp. 885–891. [9] R. McColl, O. Green, and D. A. Bader, “A new parallel algorithm for connected components in dynamic graphs,” in 20th Annual International Conference on High Performance Computing. IEEE, 2013, pp. 246– 255. [10] U. A. Acar, D. Anderson, G. E. Blelloch, and L. Dhulipala, “Parallel batch-dynamic graph connectivity,” in The 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019, pp. 381–392.

[11] Q. De Man, L. Dhulipala, A. Karczmarz, J. Łkacki, J. Shun, and Z. Wang, “Towards scalable and practical batch-dynamic connectivity,” in Proceedings of the 3rd Highlights of Parallel Computing Workshop, 2025, pp. 16–18. [12] D. D. Sleator and R. E. Tarjan, “A data structure for dynamic trees,” in Proceedings of the thirteenth annual ACM symposium on Theory of computing, 1981, pp. 114–122. [13] G. N. Frederickson, “Data structures for on-line updating of minimum spanning trees,” in Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983, pp. 252–257. [14] M. R. Henzinger and V. King, “Randomized fully dynamic graph algorithms with polylogarithmic time per operation,” Journal of the ACM (JACM), vol. 46, no. 4, pp. 502–516, 1999. [15] T. Tseng, L. Dhulipala, and G. Blelloch, “Batch-parallel euler tour trees,” in 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2019, pp. 92–106. [16] J. Soman, K. Kishore, and P. Narayanan, “A fast gpu algorithm for graph connectivity,” in 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). IEEE, 2010, pp. 1–8. [17] P. Boldi, M. Rosa, M. Santini, and S. Vigna, “Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks,” in Proceedings of the 20th international conference on World Wide Web, 2011, pp. 587–596. [18] J. Leskovec and R. Sosič, “Snap: A general-purpose network analysis and graph-mining library,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 1, pp. 1–20, 2016.