Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees

Abstract

We present the first parallel batch-dynamic algorithm for approximating coreness decomposition with worst-case update times. Given any batch of edge insertions and deletions, our algorithm processes all these updates in $\text{poly}(\log n)$ depth, using a worst-case work bound of $b\cdot \text{poly}(\log n)$ where $b$ denotes the batch size. This means the batch gets processed in $\tilde{O}(b/p)$ time, given $p$ processors, which is optimal up to logarithmic factors. Previously, an algorithm with similar guarantees was known by the celebrated work of Liu, Shi, Yu, Dhulipala, and Shun [SPAA'22], but with the caveat of the work bound, and thus the runtime, being only amortized.

SPAA 2025

References in corpus (6)

• Identification of influential spreaders in complex networks
• Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
• Parallel Batch-Dynamic Graph Connectivity
• Relevance of temporal cores for epidemic spread in temporal networks
• Parallel Batch-dynamic Trees via Change Propagation
• Parallel and Streaming Algorithms for K-Core Decomposition