大图连不连通？混杂存储稠密和稀疏，省 97% 空间

图很大、边很多的时候，想知道两个节点是否连通？传统方法空间随边数增长，新理论方法在稀疏图上反而浪费。HybridSCALE 说：把图拆开，稀疏部分无损存，稠密核心用 Sketch。

动态连通性维护是基础问题。过去几年的理论突破提出了"图 Sketch"，但实践中太臃肿。

HybridSCALE 的洞察：现实稀疏图的不均匀性——大多数边集中在少数顶点组成的稠密核心上。sketch 只编码核心，外围无损存储。BalloonSketch 进一步把 sketch 缩小 8 倍。

结果：稀疏图节省 15%，中等密度图节省 92%，稠密图节省 97%。

论文说 HybridSCALE 是"首个在真实图上节省空间的 Sketch 动态连通性算法"——这个"首个"很关键。

论文信息

• 标题：Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
• 作者：Quinten De Man, Gilvir Gill, Michael A. Bender 等
• 预印本：arXiv:2605.15173 (cs.DS)
• 论文链接：https://arxiv.org/abs/2605.15173