{"ID":2897214,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.06338","arxiv_id":"2507.06338","title":"Parallel Batch-Dynamic Algorithms for Spanners, and Extensions","abstract":"This paper presents the first parallel batch-dynamic algorithms for computing spanners and sparsifiers. Our algorithms process any batch of edge insertions and deletions in an $n$-node undirected graph, in $\\text{poly}(\\log n)$ depth and using amortized work near-linear in the batch size. Our concrete results are as follows: - Our base algorithm maintains a spanner with $(2k-1)$ stretch and $\\tilde{O}(n^{1+1/k})$ edges, for any $k\\geq 1$. - Our first extension maintains a sparse spanner with only $O(n)$ edges, and $\\tilde{O}(\\log n)$ stretch. - Our second extension maintains a $t$-bundle of spanners -- i.e., $t$ spanners, each of which is the spanner of the graph remaining after removing the previous ones -- and allows us to maintain cut/spectral sparsifiers with $\\tilde{O}(n)$ edges.","short_abstract":"This paper presents the first parallel batch-dynamic algorithms for computing spanners and sparsifiers. Our algorithms process any batch of edge insertions and deletions in an $n$-node undirected graph, in $\\text{poly}(\\log n)$ depth and using amortized work near-linear in the batch size. Our concrete results are as fo...","url_abs":"https://arxiv.org/abs/2507.06338","url_pdf":"https://arxiv.org/pdf/2507.06338v1","authors":"[\"Mohsen Ghaffari\",\"Jaehyun Koo\"]","published":"2025-07-08T18:58:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}