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

CREATORXizhe Li, Yaowei Long, David Pidugu, Thatchaphol Saranurak, Benyu Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07168

Browse the full library · About the Tower of Babel