Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
Xizhe Li, Yaowei Long, David Pidugu, Thatchaphol Saranurak, Benyu Wang · 2026
Read Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition by Xizhe Li, Yaowei Long, David Pidugu, Thatchaphol Saranurak, Benyu Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07168.txt.
Description
Xizhe Li and four co-authors build a faster connectivity oracle that survives vertex failures in a network. After a small set of vertices fails, the oracle must update quickly and then answer whether pairs of vertices remain connected. Earlier designs needed huge memory or update times that exploded with the failure count.
The new oracle updates in time depending only on the number of failures, not the graph size, and answers queries at the best possible speed. For a fixed failure count it uses near-linear space and preprocessing. The gains come from shortcutting a decomposition, reusing simpler oracles internally, and a new patch-set mechanism.
Catalog record
| CREATOR | Xizhe Li, Yaowei Long, David Pidugu, Thatchaphol Saranurak, Benyu Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 114 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.07168