Fully Dynamic Rooted Spanning Tree on GPU

Towards Faster Parallel Algorithms for Tree Decompositions

SAGA: State-Aware Graph Analytics for Combinatorial Optimization on Dynamic Graphs

This work presents SAGA, a high-performance framework for real-time combinatorial optimization on dynamic graphs that adopts a state-aware execution model in which each vertex maintains compact local state, enabling incremental and localized updates in response to graph changes.

HP-MC: Quickly Computing Maximum Clique Sizes of Large Sparse Graphs

This work presents a novel algorithm named HP-MC that, like prior approaches, is based on the branch and bound search, but which outperforms the leading maximum clique codes on large sparse graphs of various topologies by up to 10x on average.

GrAND: GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search

Modern Approximate Nearest Neighbour Search (ANNS) applications operate over continuously evolving vector collections and require graph indexes that sustain high-throughput searches while incorporating insertions and deletions with high recall. However, most GPU graph indexes are static or provide limited update support. Updates require neighbour discovery, reverse-edge creation, pruning, and deletion-induced graph repair; executing these operations concurrently introduces redundant distance computations and conflicting accesses to shared adjacency lists. Background-rebuild-based deletion further incurs substantial computation, additional memory consumption, and interference with foreground queries. We present GrAND (GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search), a GPU-native collection of dynamic-update algorithms for two popular graph indexes, Vamana and CAGRA. GrAND consolidates graph repair across a batch, eliminating redundant pruning computations, and employs a lock-free find-and-replace strategy for parallel adjacency-list updates. For reliable in-place deletion, GrAND constructs an on-demand reverse graph on the GPU, accurately identifying incoming edges without permanently duplicating the index. We evaluate GrAND on seven real-world datasets across five streaming workloads, comparing it against SVFusion and FreshDiskANN-GPU (our GPU adaptation of FreshDiskANN). GrAND improves overall workload throughput by 2.2x-8.7x and 6.5x-25.4x, respectively, while maintaining high search throughput and recall over sustained updates.

Fast and Theoretically Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps

Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic tree data structures, including Euler tour trees, UFO trees, topology trees, and rake-compress trees, are all significantly outperformed in the sequential setting by link-cut trees, which have been the sequential state-of-the-art for over 40 years. Despite their excellent performance in the sequential setting, designing efficient batch-parallel link-cut trees has remained a major open problem. In this paper, we close this gap by introducing MOJOS, a unified framework for theoretically- and practically-efficient parallel batch-dynamic trees. We exploit the fact that both Euler tour trees and link-cut trees rely on a common dynamic sequence abstraction that supports splitting and joining. We introduce a new batch-dynamic sequence built using treaps that achieves optimal work and depth, and outperforms existing parallel skip list and treap implementations for batch updates, queries, and memory usage. With MOJOS, we develop a new batch-parallel Euler tour tree algorithm that outperforms prior batch-dynamic tree implementations supporting subtree queries. Unlike prior batch-parallel Euler tour trees which rely on skip list's ability to represent cyclic sequences, MOJOS allows any batch-dynamic sequence data structure to be used as a drop-in replacement. Finally, we develop the first theoretically-efficient batch-parallel link-cut tree, which is also the first batch-dynamic data structure supporting path queries to achieve O(log n) depth for batch updates in the binary-forking model. Our link-cut tree implementation outperforms all known parallel batch-dynamic tree data structures supporting path queries.

Listing Minimal Cores in Large Real-World Graphs

Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.