跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24905 · v1

Batch-Dynamic Coreness and Applications with Logarithmic Work via Balanced Pressures

通过平衡压力实现对数工作量的批量动态核度及其应用

首次提交 2026-11-19 02:42
版本更新 2026-11-19 02:42
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

We give a parallel algorithm that maintains a one-sided (2+ε)(2+\varepsilon)-approximation of all core numbers under batches of edge insertions and deletions. For fixed ε>0\varepsilon>0, the expected amortized work is O(log⁡n)O(\log n) per edge update, and each batch has deterministic polylogarithmic depth. This improves on the previously known (4+ε)(4+\varepsilon)-approximation and O(log⁡2n)O(\log^2 n) amortized work bounds. This approximation factor approaches the factor-two limit for polylogarithmic update and query time under the OMv conjecture. Our algorithm is based on assigning each vertex a "pressure" and splits each edge's unit load smoothly between its endpoints according to their pressures. After each batch of updates, our dynamic algorithm adjusts the pressures of vertices in parallel to restore balance between the pressures and loads. We show that by maintaining balanced pressures we can obtain good approximations of core numbers. Our construction also gives a (1+ε)(1+\varepsilon)-approximation of the densest-subgraph value with logarithmic expected amortized work and supports batch-dynamic maximal matching, clique counting, forest decomposition, and coloring in low-arboricity graphs with improved or matching work bounds. We give a practical implementation of our batch-dynamic coreness algorithm and find that it is able to achieve smaller empirical error than the state-of-the-art parallel batch-dynamic implementation, while running faster. On six real-world graphs, it runs 32×32\times faster than that implementation in geometric mean and 4.1×4.1\times faster than a state-of-the-art heuristic baseline. On three graphs with up to 1.8 billion edges, it is 9.2×9.2\times faster than the heuristic baseline.

AI 论文解读

基于摘要 · 非全文审阅

提出一种并行批量动态算法,通过平衡压力以O(log n)期望摊销工作量维护所有核数的单边(2+ε)近似,并应用于稠密子图、最大匹配等问题。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 02:42 · 最新观测版本

Batch-Dynamic Coreness and Applications with Logarithmic Work via Balanced Pressures

We give a parallel algorithm that maintains a one-sided (2+ε)(2+\varepsilon)-approximation of all core numbers under batches of edge insertions and deletions. For fixed ε>0\varepsilon>0, the expected amortized work is O(log⁡n)O(\log n) per edge update, and each batch has deterministic polylogarithmic depth. This improves on the previously known (4+ε)(4+\varepsilon)-approximation and O(log⁡2n)O(\log^2 n) amortized work bounds. This approximation factor approaches the factor-two limit for polylogarithmic update and query time under the OMv conjecture. Our algorithm is based on assigning each vertex a "pressure" and splits each edge's unit load smoothly between its endpoints according to their pressures. After each batch of updates, our dynamic algorithm adjusts the pressures of vertices in parallel to restore balance between the pressures and loads. We show that by maintaining balanced pressures we can obtain good approximations of core numbers. Our construction also gives a (1+ε)(1+\varepsilon)-approximation of the densest-subgraph value with logarithmic expected amortized work and supports batch-dynamic maximal matching, clique counting, forest decomposition, and coloring in low-arboricity graphs with improved or matching work bounds. We give a practical implementation of our batch-dynamic coreness algorithm and find that it is able to achieve smaller empirical error than the state-of-the-art parallel batch-dynamic implementation, while running faster. On six real-world graphs, it runs 32×32\times faster than that implementation in geometric mean and 4.1×4.1\times faster than a state-of-the-art heuristic baseline. On three graphs with up to 1.8 billion edges, it is 9.2×9.2\times faster than the heuristic baseline.

查看此版本解读 →查看此版本原文 ↗